pad.mattdiesel.co.uk

Snippet - Prime number sieve 3

Prime number sieve 3 (C++)

Some small improvements
Created 2014-05-12 20:47:22.237420 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
34
35
36
37
#include <iostream>
#include <cmath>

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

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

    unsigned int j_max = ((unsigned int)sqrt(n)) >> 1;

    unsigned int* prime = new unsigned int[( n >> 6 ) + 1];

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

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

            if (i > j_max) continue;

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

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

    return 0;
}