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;
        primes.reserve(floor(boost::math::expint(log(max))));
        primes.push_back(2);
        for(uint64 i=3; i <= max; i+=2) {
                if(sieve[(i-3)/2])
                        continue;
                for(uint64 m=i*i; m <= max; m+=2*i)
                        sieve[(m-3)/2] = true;
                primes.push_back(i);
        }
        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.