My Project Euler prime sieving / counting code was vector<uint8_t> is_prime(n, true); // Sieve for (uint64_t k = 3; k * k < n; k += 2) if (is_prime[

My Project Euler prime sieving / counting code was vector<uint8_t> is_prime(n, true); // Sieve for (uint64_t k = 3; k * k < n; k += 2) if (is_prime[k]) for (uint64_t multiple = k * k; multiple < n; multiple += 2 * k) is_prime[multiple] = false; It only loops over odd numbers; it only crosses off odd multiples of prime numbers. Note the stop condition of the outer loop and starting point of the inner loop. Note that this code is memory-bound. You can get nearly 10x speed up if you implement a segmented sieve (sieving [2,n] in intervals, keeping memory costs more or less fixed)