Optimizing the Sieve of Eratosthenes for prime generation

Question

I've been on a Project Euler spree and I've been solving problems and as you might know, many of them require you to use prime numbers. I've been using the following code to generate and store primes in a vector, but was wondering if there is any non-obvious speed-ups that will make a large difference on the runtime of the generation.

// Generate the primes upto N using the Sieve of Eratosthenes.
template<typename T>
std::vector<T> generatePrimes(T n) {
    std::vector<T> result = std::vector<T>();
    if(n < 2) {
        return result;
    }
    std::vector<int> input(n + 1, 1);
    // Calculates the upper limit of the numbers to check.
    T sqrtN = (T)sqrt(n);
    // Iterate till the square root.
    for(T i = 2; i <= sqrtN; i++) {
        if(!input[i]) {
            continue;
        }
        // Multiples are marked false.
        for(T j = i * i; j <= n; j += i) {
            input[j] = 0;
        }
    }
    // Add to result vector.
    result.push_back(2);
    for(T i = 3; i <= n; i += 2) {
        if(input[i]) {
            result.push_back(i);
        }
    }
    return result;
}

And it is called like so:

vector<unsigned int> primes = generatePrimes<unsigned int>(10'000);

Is there any other way to speed this up? Before I had changed a line where I create the input vector to int from bool and it resulted in a nice 2.3x speed increase. See here for benchmark.

Answer 1

A few things to consider:

Is having the function generic really necessary? Why not just make the data type unsigned long long instead? This way you can do some bounds checking.

I would suggest using a bitset to hold the raw data would be more efficient than using 32 bits to represent each 1 or 0.

All primes are odd except for 2. If you add 2 to the result vector, you can start the outer loop at 3 and increment by 2.

Since the outer loop will only be odd numbers the start of the inner loop will also be odd. Therefore in order to keep hitting the odd number multiples you can increment by i*2.

You can shorten the second loop by adding to the vector every time you find a prime in the outer loop. This way the second loop can start where the outer loop finishes.

There is also another algorithm you can use that is more highly optimised for making a list of primes, mind you it's also more complicated( sorry I can't remember the name off hand)

Answer 2

You can make it go quite a bit faster by using wheel factorization to eliminate processing or storing multiples of small primes. As @tinstaaf said, you can easily eliminate the even numbers and deal with 2 as special case when you're almost done.

You can consider an odds-only sieve as the first level of wheel factorization. A mod 6 wheel eliminate multiple of 2 and 3, a mod 30 wheel eliminates multiples of 2, 3, and 5, and is a sweet spot. If you look at numbers starting with 7 and skip multiples of 2, 3, and 5, only 8 out of the next 30 can possibly be prime. Since there are 8 bits in a byte, one byte can represent 30 prime candidates so you can squeeze a lot of data about primes into a small bit array.

But prime wheels beyond odds-only are more complex. Wikipedia has a good introduction to the subject.