int i, 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)

6 Years
Discussion Span
Last Post by Distantearth

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

Edited by daviddoria: n/a


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


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

Edited by StuXYZ: n/a


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 )

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.