C++ prime number questions

This is a discussion on C++ prime number questions within the C++ Programming forums, part of the General Programming Boards category; I came across this code to find prime numbers and I don't quite understand the nested for loop. Can someone ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    120

    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. #2
    Registered User MrMatt027's Avatar
    Join Date
    Nov 2010
    Location
    USA, Florida
    Posts
    21
    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 10:08 PM.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,198
    Quote Originally Posted by MrMatt027 View Post
    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.
    Right 98% of the time, and don't care about the other 3%.

  4. #4
    Registered User MrMatt027's Avatar
    Join Date
    Nov 2010
    Location
    USA, Florida
    Posts
    21
    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 10:27 PM.

  5. #5
    Registered User
    Join Date
    Dec 2009
    Posts
    120
    Quote Originally Posted by grumpy View Post
    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. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,198
    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 .....
    Right 98% of the time, and don't care about the other 3%.

  7. #7
    Registered User
    Join Date
    Dec 2009
    Posts
    120
    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. #8
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help creating prime number program
    By dauden6 in forum C++ Programming
    Replies: 4
    Last Post: 07-17-2009, 02:50 PM
  2. Calculating next prime number
    By anilemon in forum C Programming
    Replies: 8
    Last Post: 04-17-2006, 10:38 AM
  3. prime number.
    By tdoctasuess in forum C Programming
    Replies: 13
    Last Post: 05-13-2004, 08:03 AM
  4. Replies: 6
    Last Post: 11-04-2002, 04:11 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21