C++ Prime numbers task

[literal]

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";
    }

}

Can somebody experienced clear me how this program actually finds prime numbers...
The line with the last if condition confuses me most -> j > (i/j)

[daviddoria]

This line if(!(i%j)) break; says "if you can divide i by j evenly (with no remainder), i is not prime". It could be more clearly expressed as if(i%j == 0) break; I'll leave the next line for someone else :)

[StuXYZ]

Ok this code made me laugh -- I had better explain.

So let us consider each line in turn [note i have expanded the formatting]

for(int=2;i<1000;i++)         // Simple loop
   {
      for(j=2;i/j;j++)        // Loop to do j=2 to j < i : it works because
                              // integer arithmetic is being used

The i/j uses the fact that integer division ignores the division remainder,
e.g. 5/2 == 1 but 3/4 ==0 . Just writing i/j also uses the fact that any integer other than 0 is true.

To see the effect of i/j consider this

i  j   i/j  
8  1    8     
8  2    4     
8  3    2     
8  4    2
8  5    1
8  6    1
8  7    1
8  8    1
8  9    0

Continuing

// continued from above:
if (!(i%j)) break;           // if j is a factor of i , exit the inner (j) loop.
if (j>(i/j))                 // Test to see if all possibilities for have been 
                             // used since you don't need to test beyond sqrt(i) 
                             // Anything beyond that means it must be a prime

Note that (j>(i/j)) is a way of saying j*j>i . I think that latter is clearer

Hope that helps...

I guess I was more surprised by the way the whole code was written in a divisional style.

[literal]

Why is the (j > i/j) condition that decides if the number is prime...

[daviddoria]

Did you read the previous post? StuXYZ spent a lot of time explaining it for you!

// Test to see if all possibilities for have been used. You don't need to test beyond sqrt(i).

[NathanOliver]

What it is doing is testing if you broke the loop or ran to the end. If you ran to the end of the loop than if (j > (i / j)) will be true. If you broke the for loop because if (!(i % j)) returned true than if (j > (i / j)) will be false and the nymber is not prime.

[Distantearth]

Look my friend literal. Lets say there is a int number P and there is another int number C such as C^2>P but (C-1)^2<P
Then if the P has a divisor Q (Q|P) and if this Q is greater than C
It follows that an int number K such as Q*K=P would exist.
And this number K would be smaller than C
However the algorithm checks all the numbers smaller than C
( that's because C<(P/C)= C^2<P )