# C++ prime number questions

• 12-03-2010
nick753
C++ prime number questions
I came across this code to find prime numbers and I don't quite understand the nested for loop. Can someone explain exactly how it works? If i and j both = 2, then how does j increment when j < i (since 2 isn't less than 2)? Please take a look.

Code:

```#include <iostream> using namespace std; int main() {       int flag = 0;       for(int i = 2; i <= 100; i++)   {     for(int j = 2; j < i; j++)     {           if( i % j == 0)                     flag = 1;     }     if(flag == 0)     cout << i << endl;     flag = 0;   }                 cin.get();           return 0;   }```
• 12-03-2010
MrMatt027
Well, I might be wrong, but I think in this for loop it's stating that j < i and not asking.
So, it doesn't matter what i is, j will keep increasing.
You're right though, numerically 2 isn't less than 2.
• 12-03-2010
grumpy
Quote:

Originally Posted by MrMatt027
Well, I might be wrong, but I think in this for loop it's stating that j < i and not asking.

Not even close. It's saying the second loop will be executed while j < i. j will be compared with i every time the body of the inner loop is executed.

Which means that, if i is 5 (in the outer loop) then the inner loop will keep incrementing j until it has a value of 5. If i is 150, the inner loop will keep incrementing j until it has a value of 150.

If i is 2, the inner loop will not be executed (as j starts with the value 2, which is not less than 2).

For each value of i, all the inner loop is doing is setting flag to be 1 if i is exactly divisible by any integer 2 and i.
• 12-03-2010
MrMatt027
Oh I see, my bad. Honestly, I couldn't figure out why j was ever in that until you said it was to set the flag.
Thank you grumpy.
• 12-04-2010
nick753
Quote:

Originally Posted by grumpy
It's saying the second loop will be executed while j < i. j will be compared with i every time the body of the inner loop is executed.

If i is 2, the inner loop will not be executed (as j starts with the value 2, which is not less than 2).

So how does the inner loop ever first get executed since i and j are both set to 2? Does the outer loop get executed first, then the inner loop starts? I just don't understand how the inner loop starts it's execution because 2 is not less than 2?
• 12-04-2010
grumpy
The first time through the outer loop, i has value of 2 so the inner loop body is not executed. But the subsequent code (testing flag and output, resetting flag) is executed, so the value of 2 is output.

i is then incremented to 3. 3 is <= 100 so the outer loop body starts again. This time, j starts with a value 2 which is less than 3, so the body of the inner loop is executed .....
• 12-04-2010
nick753
Ok now how is the i%j logic working? Say i is 4, then j would be 3 right? 4%3 does not equal 0 right? And when i is 6, wouldn't j be 5? Then 6%5 would not equal 0 either? What am I missing?
• 12-04-2010
User Name:
It tests if i is divisible(i is divisible by j when i%j == 0) by any number between 2 and i - 1, inclusively. That's what the inner loop is for, it iterates j through the aforementioned set. You could increase the efficiency by sqrt if you make j iterate from 2 to the integer square root of i.