Sieve of Erastosthenes in C++ and STL

Remco Bloemen

2009-11-23, last updated 2014-03-04

The von Staudt-Clausen implementation in one of my previous posts required a list of small primes. A fast way to calculate them is using the Sieve of Erastosthenes. Here’s an efficient implementation in C++ and STL:

vector<uint64> prime_sieve(uint64 max)
        vector<bool> sieve((max+1)/2);
        vector<uint64> primes;
        for(uint64 i=3; i <= max; i+=2) {
                for(uint64 m=i*i; m <= max; m+=2*i)
                        sieve[(m-3)/2] = true;
        return primes;

This implementation employs a number of well known tricks:

If you need something faster than this, you could look into the Sieve of Atkin and D. J. Bernsteins implementation.