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 :)
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 usedThe 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 0Continuing
// 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 primeNote 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 )
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.