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

5
Contributors
6
Replies
7
Views
6 Years
Discussion Span
Last Post by Distantearth
Featured Replies
  • 2

    Ok this code made me laugh -- I had better explain. So let us consider each line in turn [note i have expanded the formatting] [code=c++] 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 … Read More

0

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

2

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.

Edited by StuXYZ: n/a

0

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

-1

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

1

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.

-1

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.