pad.mattdiesel.co.uk

Snippet - Prime number seive

Prime number seive (C++)

Finds prime numbers using a seive method.
Created 2014-05-11 00:48:20.617830 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 = 0x7FFFFFFF; // Maximum value for int32.
    unsigned int i, j;

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

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

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

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

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

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

    return 0;
}