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 11:08 PM.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,638
    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%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  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 11: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,638
    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%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  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, 03:50 PM
  2. Calculating next prime number
    By anilemon in forum C Programming
    Replies: 8
    Last Post: 04-17-2006, 11:38 AM
  3. prime number.
    By tdoctasuess in forum C Programming
    Replies: 13
    Last Post: 05-13-2004, 09:03 AM
  4. Replies: 6
    Last Post: 11-04-2002, 05:11 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM

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