``````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)

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 :)

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.

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

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).

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.

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 )

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.