/ Published in: C++

Expand |
Embed | Plain Text

#include <iostream> using namespace std; int main() { int i, j; for ( i = 2; i < 100000; i++ ) { for ( j = 2; j <= i/2; j++ ) { if ( ! ( i % j ) ) break; } if ( j > i / 2 ) cout << i << endl; } return 0; }

## Comments

Subscribe to commentsYou need to login to post a comment.

could u explain how the function works?

Yes.

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.

Thank you,your code is beatiful and smart.

*beautiful