Prime numbers confusion

[constantx]

Can someone explain me the following code:

int i, j;
 
for(i=2;i<1000;i++){
    for(j=2;i/j;j++){
        if(!(i%j)) break;
    if(j>(i/j)) cout<<i<<" is prime\n";
    }
 
}

The last line/if is the reason of my confusion; how does it decide what num is prime and when?

[spaggy]

To be honest i don't like this code. Although it's being a little clever, it's not very clear what it's doing. The last line can works because to check if a number, x, is prime you only need to check if it is divisible by any number between 2 up to it sqrt(x). if n > (x / n) then n > sqrt(x), i hope it's easy to see why. So the last line effectively says if i've check all numbers up to sqrt(i) then i and i is not divisible by any of these numbers i must be prime.

[spaggy]

Although it's being a little clever

Actually i take that back because even though it's already determined a number is prime it at j > (i/j) it still carries on checking until j > i. So i suspect for a number like 49, it will print out

49 is prime

quite a few times. Never make code more complicated than it needs to be.

[Kyon]

http://www.cplusplus.com/forum/general/25817/
Kinda already pointed this out over here, figured this topic was double posted.

bool IsPrime(unsigned long int x)
{
    unsigned long int i = 2;
    while(i < ((x/i)+1))
    {
        if ((x%(i++))==0)
           return false;
    }
    return true;
}

Works a charm.

[constantx]

I made some typo; the original source code from the book is:

int i, j;
	for(i=2; i<1000; 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";
}

[spaggy]

In which case the code is good and not silly as i had thought

[constantx]

One more thing: When would 1st if condition actually break the non-prime number; I mean would the non prime number reach the last 'if' if it's not prime... When you put cout in between two if's
you'll see that the non-prime e.q. 4 is not broken or tossed away ??

[Athar]

The loop breaks when j divides i (the condition in its proper form is i%j==0).

[constantx]

Then what's the point of breaking 'if'; if the non prime number will be passed to the second if and then it'll be eliminated? Before testing I thought that the non-prime would be eliminated as soon after reaching the break condition; after testing I realized that it's still actually tested against the second nested if; so it's not broken even after confirming that the number is not prime?!

[Kyon]

The break; literally means that if its a possible divisor for i, break out of the loop and go on with a different i (which is i incremented with 1). The second if will be reached whenever there are no possible divisors j in between 2 and int(i/j).

[constantx]

Edit; I've posted some more details of confusion

[Athar]

The break only breaks the inner loop, not the outer loop.
Since the second if is in the outer loop, it will always be reached. It checks whether the loop ran through without breaking. If so, that means no divisor was found and the number is prime.

[constantx]

Aren't both loops inner ones, if they're between brackets?

[Athar]

By that definition, there would be no outer loops.
Doesn't matter either way, break and continue only refer to the most inner loop they appear in.

[constantx]

In other words it only breaks 2nd for?

[Zhuge]

I suppose you could put it that way.