Posted By

gdonald on 09/27/06


number generator prime

Versions (?)

Who likes this?

3 people have marked this snippet as a favorite


C++ prime number generator

 / Published in: C++

  1. #include <iostream>
  2. using namespace std;
  4. int main()
  5. {
  6. int i, j;
  8. for ( i = 2; i < 100000; i++ )
  9. {
  10. for ( j = 2; j <= i/2; j++ )
  11. {
  12. if ( ! ( i % j ) ) break;
  13. }
  15. if ( j > i / 2 ) cout << i << endl;
  16. }
  18. return 0;
  19. }

Report this snippet  


RSS Icon Subscribe to comments
Posted By: Sweety on March 2, 2007

could u explain how the function works?

Posted By: ejexion on February 22, 2011


Starting with the first for-loop, we can see that, obviously, we are only testing for primes in [ 2 , 100000 [ . Nothing too complicated there.

The next loop goes through the numbers that will be potential factors of our number 'i'. Starting with 2, this value takes on larger and larger values, up to half of 'i' plus 1. The 'if' statement within that for-loop serves to stop checking if a number is prime as soon as it is evenly divided by j.

Finally, the last statement merely checks if j is bigger than half of i, and if it is, then i is a prime.

All of that explanation doesn't really explain why this works. I'll try to get that across here.

The for-loop with i in it can't be made any clearer; it is simply the number that we are checking for primality. What happens inside that outer for-loop is the interesting stuff. Basically, when a number is prime, the inside for-loop will run until j is equal to half of i (rounded down) plus 1. If a number is not prime, it will "break" out of the if statement !( i % j ), since that statement is TRUE when i % j is 0. So there are two ways that a number can arrive at the last if-statement; either by being prime (and consequently j being greater than i/2) or by not being prime and j being less i/2. Once that last if-statement is arrived at, it's clear that only primes will be printed out.

Posted By: advanceuser on July 2, 2011

Thank you,your code is beatiful and smart.

Posted By: advanceuser on July 2, 2011


You need to login to post a comment.