Optimizing the Sieve of Eratosthenes for prime generation 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&lt;typename T&gt;
std::vector&lt;T&gt; generatePrimes(T n) {
    std::vector&lt;T&gt; result = std::vector&lt;T&gt;();
    if(n &lt; 2) {
        return result;
    }
    std::vector&lt;int&gt; 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 &lt;= sqrtN; i++) {
        if(!input[i]) {
            continue;
        }
        // Multiples are marked false.
        for(T j = i * i; j &lt;= n; j += i) {
            input[j] = 0;
        }
    }
    // Add to result vector.
    result.push_back(2);
    for(T i = 3; i &lt;= n; i += 2) {
        if(input[i]) {
            result.push_back(i);
        }
    }
    return result;
}


And it is called like so:

vector&lt;unsigned int&gt; primes = generatePrimes&lt;unsigned int&gt;(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.
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)