# Thread: C++ prime number questions

1. ## 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;

}```

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

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

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

5. 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?

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

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

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