pad.mattdiesel.co.uk

Snippet - Prime number seive 2

Prime number seive 2 (C++)

Prime number seive for first 200 million primes.
Created 2014-05-11 17:36:52.956250 by Matt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>


int main( int argc, char const* argv[] )
{
    const unsigned int n = 0xFFFFFFFF; // Maximum value for int32.
    unsigned int i, j;

    const int printevery = 10000;
    int x = printevery;
    int count = 1; // 2 is a prime.

    char* prime = new char[( n >> 4 ) + 1];

    for ( i = 1; i < n>>1; i++ ) {
        if ( !( prime[i >> 3] & ( 1 << ( i & 7 ) ) ) ) {
            count++;

            if ( !--x ) {
                std::cout << (i << 1)+1 << std::endl;
                x = printevery;
            }

            for ( j = (i << 1) + 1 + i; j < n>>1; j += (i << 1) + 1 ) {
                prime[j >> 3] |= 1 << ( j & 7 );
            }
        }
    }

    std::cout << "Found " << count << " primes." << std::endl;

    return 0;
}