kuoe0
1/11/2012 - 2:34 PM

[Prime] Sieve of Eratosthenes - http://kuoe0.ch/1209/prime-sieve-of-eratosthenes/

[Prime] Sieve of Eratosthenes - http://kuoe0.ch/1209/prime-sieve-of-eratosthenes/

#include <cstdio>
#include <cstdlib>
using namespace std;
#define MAX 1000000
bool isNotPrime[ MAX + 1 ];
void sieve() {
    memset( isNotPrime, 0, sizeof( isNotPrime ) );
    isNotPrime[ 0 ] = isNotPrime[ 1 ] = 1;
    for ( int i = 2; i <= MAX; i += 2 )
        isNotPrime[ i ] = 1;
    for ( int i = 3; i * i <= sqrt( MAX ); i += 2 )
        if ( !isNotPrime[ i ] )
            for ( int j = i + i; j <= MAX; j += i + i )
                isNotPrime[ j ] = 1;
}
int main() {
    sieve();
    for ( int i = 0; i <= MAX; ++i )
        if ( !isNotPrime[ i ] )
            printf( "%d\n", i );
    return 0;
}