loops

[Jacobhaha]

hello i have spent many hours trying to figure out how this works,
can someone help me understand this and explain it to me as if i were 2 years old? hehe

  int i, j;

for(i=2; i<100; i++)
{
    for(j=2; j <= (i/j); j++)
    {
    if(!(i%j))
        break; // if factor found, not prime
    if(j > (i/j))
        cout << i << " is prime\n";
    }
} 

[Zhuge]

Why don't you try explaining it first, so we can figure out where you are having trouble? Then we can focus on explaining that part.

[Jacobhaha]

well i don't understand most of it, i understand that
i = 2 and i < 100 gives it a cap and i++ adds one to i every run
j = 2 and here comes one part i dont understand "j <= (i/j);" because j also has
j++ so it will also go up every run? so they must be equal and i/j will then be two equals number so that must be 1? why initialize it to be 2? the condition in j will then be false all the time?

another part i dont understand is if(! (i%j)) if there is mod when you divide i with j? (which there will never be because they are equal?) you make it false with ' ! ' ? and if it false you break that if statement?

and another part i dont understand is in the second if statement it says that, if j is bigger than i/j (which is 1 i guess?)
then cout i? It really confuses me.. :)

hope you can help me here ^^

[discofire]

Almost... but your for loops don't only iterate once. Each loop operates somewhat independently of the other. The inner loop doesn't have visibility to the outer loop, and will run until it's exit condition is met. It will also run it's entire loop each time the outer loop iterates.

So you have your first for loop

for(i=2; i<100; i++) { ... }

That will run whatever is between the { } braces 100 times (provided you don't change the value of i within the loop itself.

Then you have another nested for loop:

for(j=2; j< (i/j); j++) { ... }

That will loop until j > (i / j)

Your first for loop enters it's code block with an initial value of i being 2.
It then executes the second for loop from j=2 to j > 2/2; So the first iteration it does nothing.

in fact, the first few iterations of i do nothing, and your outer for loop goes through just incrementing i.

Then lets assume i=11.

Your nested for loop always reinitializes j to 2, so it will start it's loop and will run from j=2 to j > 11/2 => 5.5
if(!(11%2)) is false since 11%2 is 1 (true), but the ! negates the expression and makes it false.

j > 11/2 is also false, so nothing prints for j=2
keep incrementing j
j=3, 11/3 => 3.666
j=4, 11/4 => 2.75
EXIT since 4 <= (11/4) is now false

This means you will never reach the cout statement printing your prime number since j > (i/j) can never be reached in your for loop. The for loop exits when j > (i/j)

[Jacobhaha]

So j will run until j > 11/2 which is = 5.5
11/3 = 3.666
11/4 = 2.75 , so here 4 > 2.75 here j is greater than i and 3 modulus? so i%j is true and then again false because of ' ! ' , and if it is false, it break.
you said: " EXIT since 4 <= (11/4) is now false " , you lost me there.

[discofire]

Your exit condition in for(j=2; j <= (i/j); j++) is recomputed after each iteration. When i==11, and j==4, j <= (i/j) => 4 <= 11/4 => 4 <= 2.75 which is false, so your for loop terminates.

Your inner for loop will never process j=5, 6, 7, 8... It will stop at 4, and in fact will only process j=1,2,3 when i==11.

The code you have:

    if(j > (i/j))
        cout << i << " is prime\n";
    }

can never be reached because j > (i/j) can never be true inside your for loop. The exit condition being j <= (i/j) forbids it.

j > (i/j) and j <= (i/j) cannot be true at the same time.


j is incremented after each iteration through the for loop, and as such, the value of i/j is also changing. I suspect you want your for loop to exit on a set value. Try doing something like this:

int i, j;

for(i=2; i<100; i++)
{
    int half = i/2;
    int found = 1;
    for(j=2; j <= half; j++)
    {
      if(!(i%j)) {
          found = 0;
          break; // if factor found, not prime
      }
    }
    if(found)
        cout << i << " is prime\n";
}

For a better understanding of what's going on in your code, print out each value of i and j with this and look at the output:

#include <iostream>

using namespace std;

int main() {
  int i, j;
  for(i=2; i<10; i++) {
    cout << "i = " << i << endl;
    for(j=2; j<10; j++) {
      cout << "j = " << j << endl;
    }
  }
}

EDIT: had the found var backwards. should be initialized to 1 and set to 0 in your check.

[Jacobhaha]

but if you remove brackets from second for loop it works when i execute it?

[discofire]

The brackets are still there. I only took the if check out of that loop because you can't determine if a number is prime or not until you've done an exhaustive search. And that search isn't complete until the inner for loop exits. So I set a variable if you determine it is not a prime (found=0), but if the inner for loop completes and does not set found=0, then it must be a prime since no factors were found.

The inner loop starts on line 7 and ends on line 13. The braces are on lines 8 and 13. The outer for loop starts on line 3 and ends on line 16.

[Jacobhaha]

So, when :
i = 2 - j = 2, and increment up till the cap , is there something wrong in the code given by my tutorial the link is : http://www.tutorialspoint.com/cplusplus/cpp_nested_loops.htm , if you could check it out, they are saying it works.

[discofire]

I was simply expanding on what j <= (i/j) is. Just fill in the blanks. you know what i and j are at any given iteration through the loop. In your code, your exit condition is changing each time through the inner loop. Run the small program I posted so you can see how the nested for loops are executed.

j <= (i / j) is equivalent to 4 <= 2.75 when you plug i==11 and j==4 into that equation. That's all I was pointing out in that.

However, the exit condition in your for loop is still j <= (i / j), but within your for loop you have an if statement checking for j > (i / j). That can never happen since your for loop will exit before that case exists.

[discofire]

That example is very misleading. The problem is partly with their indentation, and partly with not using braces around the inner for loop. The if statement is not part of the inner for loop. Only the single statement following the for loop in their example is part of the for loop.

How it is written:

#include <iostream>
using namespace std;

int main ()
{
   int i, j;

   for(i=2; i<100; i++) {
      for(j=2; j <= (i/j); j++)
        if(!(i%j)) break; // if factor found, not prime
        if(j > (i/j)) cout << i << " is prime\n";
   }
   return 0;
}

How it should be written:

#include <iostream>
using namespace std;

int main ()
{
   int i, j;

   for(i=2; i<100; i++) {
      for(j=2; j <= (i/j); j++) {
        if(!(i%j)) break; // if factor found, not prime
      }
      if(j > (i/j)) cout << i << " is prime\n";
   }
   return 0;
}

[Jacobhaha]

I did run your program and tried something:
i scrolled down to i = 9 and j = 2 and then j <= (i/j) becomes true? and if its true the if statement in that loop will run right? so if if (! (i%j)) is false(if there is no mod) because that means it will divide equally, so it will break,
but if j <= (i/j) is false it will jump down to the if statement in the first loop right? and if if (j > (i/j)) e.g. 9/5 = 1.8 and j = 5 so it becomes true and it will cout i even though 9 is not prime?
is this right or am i still wrong?

[discofire]

For i=9 j=2, 2 <= 9/2 (4.5) is true. The if statement however is not. i%j is 9%2 == 1 which is true, but the ! changes the boolean value to false, so the break does not happen. At that point, the loop will continue to j=3. That will also run since 3 <= 9/3 (3). In that case however, 9%3 == 0 which is false. The ! in that case makes the if statement true, and the break will happen at that point.

The next if statement then is j > i/j or 3 > 9/3 which is false since 3 > 3 is false. So nothing should print out for that one.

[Jacobhaha]

Ahh, so if the for(j=2; j <= (i/j); j++) { is not true, it will not even check if if(!(i%j)) is true, just move on to the if(j > (i/j)) cout << i << " is prime\n"; and check if thats true in the first for loop?

[Chervil]

I don't know if this has already been mentioned. In the tutorial pages there is a detailed description of the operation of the for loop.

for (initialization; condition; increase) statement;

The role of each of the four parts is described, and importantly, the sequence in which this is done:

http://www.cplusplus.com/doc/tutorial/control/

[Jacobhaha]

ok i take a look at it thanks.