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; }
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.
Last edited by MrMatt027; 12-03-2010 at 11:08 PM.
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.Originally Posted by MrMatt027
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.
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.
Last edited by MrMatt027; 12-03-2010 at 11:27 PM.
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?
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 .....
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?
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.
