CODEWITHSUNDEEP
c++loopsfor-loopnestedprimes
Jacob
Jacob

Reputation: 61

Nested loops and prime numbers

Hello I have spent many hours now trying to figure out how this example given by my tutorial works, and there is a few things I don't understand and yes i have searched the web for help, but there is not much when it is this specific example i really want to understand.

The first thing I don't understand is that 'i' and 'j' = 2 and both the for loops has i++ and j++, won't that make 'i' and 'j' equal all the time? So in the second for loop, if 'j' has to be less than e.g.. 4/4 = 1 then it has to be less than 1? when it has been initialized to be 2. 

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";
    }
}

Upvotes: 2

Views: 2609

Answers (4)

Jon Simpkins
Jon Simpkins

Reputation: 152

It doesn't look like the existing code will actually ever declare i to be prime, because of the upper limit on j. The cout statement that declares i to be prime triggers when j > (i/j), but j only is incremented up to (i/j) (it currently will never be greater than (i/j), even if i is prime).

Try adjusting the inner loop to be:

for (j = 2; j <= ceilf(float(i)/float(j)) + 1; j++)

or something along those lines.

Upvotes: 0

emacoder
emacoder

Reputation: 9

The code is searching for all the prime numbers between 2 and 99, so i and j are initialized to 2.*

Understood that, the first for loop try if every number between 2 and 99 is prime, using the second for loop, which searches for divisors of i.

If the second for loop doesn't find divisors, then i is prime.

The two nested loop don't have the same value because they are nested! So when i = 2, j=2, then j=3(and i is still 2), then j=4,(i is still 2)........then j=99, so the second loop is ended,then also the first for loop increment : i=3, j=2, then j=3(i is still 3) ..... Hope i've been clear :) Ask for doubts!

Upvotes: 0

Logicrat
Logicrat

Reputation: 4468

The for loop on j will execute it full range for each and every value of i. so no, they will not always be equal.

And yes, when the value of i is low, the loop on j will not even get started, but then as i takes on progressively higher values, the loop on j will run a little longer for each value of i.

Just for example, think of the case i == 81. Then j will take on values in the range [2..9]

Upvotes: 1

kviiri
kviiri

Reputation: 3302

both the for loops has i++ and j++, won't that make 'i' and 'j' equal all the time?

Nope! i++ increments the outer loop, and j++ increments the inner loop. For each round of the outer loop, the inner loop can be iterated (and thus incremented) several times. So for every round of the outer loop, j goes through values from 2 to i/j in the inner loop.

I recommend you to try this code out in a debugger, or simulate it on pen and paper to understand what's happening.

Upvotes: 4

Related Questions