I don't understand how this program find prime numbers

Ryan15 (20)
How does this program find prime numbers and why doesn't the loop stops after it encounters the break statement?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>
 
using namespace std; 
int main () {
   int i, j;
   
   for(i = 2; i<100; i++) {
      for(j = 2; j <= (i/j); j++){
         if(!(i%j)) break; // if factor found, not prime
      }
         if(j > (i/j)) cout << i << " is prime\n";
      
   }
	
    return 0;
}
JLBorges (13770)
Try running this noisy version of the program and studying its output.
(To reduce verbosity of the output, it tests for prime numbers in the smaller interval [70,99])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <iostream>

using namespace std;

int main () {

    int i, j;

    cout << "find prime numbers in [70,99]\n=============================\n\n" ;

    for(i = 70; i<100; i++) {

        cout << "\nouter loop: i == " << i << '\n'
             << "    enter inner loop, test divisibility by " ;

        for(j = 2; j <= (i/j); j++){

            cout << j << ", " ;
            if( !(i%j) ) // if factor found, not prime
            {
                cout << "factor found (" << i << '/' << j << "), not prime, break" ;
                break ;
            }
        } // *** end inner loop ***

        cout << "\ninner loop ended with j == " << j ;

        if( j > (i/j) ) {

            cout << ", " << j << " > (" << i << '/' << j << ")\n"
                 << "********* ergo " << i << " is prime *********\n";
        }

        else {

            cout << ", " << j << " <= (" << i << '/' << j << ")\n"
                 << "ergo " << i << " is not prime\n";
        }
    } // *** end outer loop ***
}
Ganado (6812)
break breaks out of the inner-most loop. It won't break out of both nested loops.

!(i%j) means (i % j == 0), meaning "i divisible by j" (or "j divides i").
Last edited on
Topic archived. No new replies allowed.