Prime numbers

[constantx]

How this code actually works

int i, j;

	for(i=2; i<16; i++) {
		for(j=2; j<=(i/j); j++) //confused
			if(!(i%j)) break ;
		if(j>(i/j)) cout<<i<<" / "<<j<<endl; //even more
                  }

[jsmith]

What's so confusing?

Try adding a few print statements to help you figure out how it works. It is not too complicated.

[supertrooper]

int i, j;

for(i=2; i<16; i++) {
for(j=2; j<=(i/j); j++)  // j ranges from 2 up to square root of i.  this is because the program is testing for divisors of i.

if(!(i%j)) break ; // if j divides i then stop

if(j>(i/j)) cout<<i<<" / "<<j<<endl;      // if the condition of the for loop has been broken (i.e. the loop completed without the break) then output.  The loop would only get this far if i was prime
}
 

[moorecm]

http://cplusplus.com/doc/tutorial/control/

[constantx]

Is this true: "You can stop at the value
of i / j because a number that is larger than i / j cannot be a factor of i"

[jsmith]

j <= i / j

using simple algebra:

j^2 <= i

If N has exactly two factors A and B, A <= B, it is easy to see that A must be no more than sqrt( N ), since
if that were not true, then A * B must be greater than N.

If N has more than two factors A₁ <= A₂ <= ... A_n, then
it also follows that the smallest of these factors, A₁, must also be less than or equal to
sqrt( N ), since otherwise A₁ * A₂ * ... * A_n must be strictly
greater than N.

Therefore, one can write an algorithm that brute force checks all values <= sqrt( N ) and be
ensured that the algorithm will find all factors of N.

[constantx]

Can you include actual numbers, it'd be easier to comprehend; e.g. from 2 to 7