Sieve of eratosthenes with std::vector
Aside from the other optimizations, if you are using the sieve to check for primality of a number, you can optimize further, every prime after 2 is odd, therefore any even number that isn't 2 is not prime. This can easily be checked without the sieve.  I would suggest that marking all the even numbers false is superfluous.  So mark 2 as true and start the outer loop at 3 and increment by 2. As was mentioned, the inner loop can start at i*i, and since this will be an odd number you only need to mark every other multiple, therefore you can increment by i*2.  Something like this:

std::vector&lt;bool&gt; sieve_of_eratosthenes(int n)
{
    std::vector&lt;bool&gt; primes(n+1, true);
    primes[0] = false;
    primes[1] = false;
    int limit = (int)sqrt(n) + 1;
    for (int i = 3; i &lt; limit; i += 2)
    {
        if (primes[i])
        {
            int step = i * 2;
            for (int j = i * i; j &lt;= n; j += step)
            {
                primes[j] = false;
            }
        }
    }
    return primes;
}