Prime Sieve and brute force Got caught up with this morning's C++ question.
So I thought I would have a go.

SO here is my attempt at printing the first 1001 primes.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;

bool isPrime(std::size_t num, std::vector&lt;std::size_t&gt; const&amp; primes)
{
    std::size_t max = std::sqrt(num);
    for(auto const&amp; prime: primes)
    {   
        if (prime &gt; max) {
            return true;
        }   
        if (num % prime == 0)
        {   
            return false;
        }   
    }   
    return true;
}

std::size_t sieve(std::size_t size, std::vector&lt;std::size_t&gt;&amp; results)
{
    // primeCandidates holds 0/1 for each potential prime candidate.
    // The index represents the potential prime (index * 2 + 1)
    // This allows us to ignore all factors of 2
    // max is one past the highest prime candidate we can test for and store in primeCandidates
    std::size_t const           max = size * 2 + 1;
    std::vector&lt;std::size_t&gt;    primeCandidates(size, 1); 

    // Add some default well know primes.
    results.push_back(2);
    results.push_back(3);

    // We will use the technique of incrementing by 2 then 4 then 2 then 4
    // This means skip all factors of 2 and 3 automatically.
    std::size_t       inc = 2;
    std::size_t loop = 5;
    for(; loop &lt; max; loop += inc, inc = 6 - inc) {
        std::size_t index = loop/2;

        // If we find a candidate that is valid then add it to results.
        if (primeCandidates[index]) {
            results.push_back(loop);

            // Now strain out all factors of the prime we just found.
            for(; index &lt; primeCandidates.size(); index += loop) {
                primeCandidates[index] = 0;
            }   
        }   
    }   
    return loop;
}

int main()
{
    std::size_t constexpr   primeRequired   = 1001;
    std::size_t constexpr   siveStartSize   = 1000;

    std::vector&lt;std::size_t&gt;    result;
    result.reserve(primeRequired);

    // Use the Sieve of Eratosthenes to get a basic set of primes.
    std::size_t next = sieve(siveStartSize, result);

    // Want to re-use the 2/4/2/4 increment pattern
    // So work out the correct start point and increment value.
    std::size_t inc  = next % 6 == 5 ? 2 : 4;

    // We now use brute force checking each number against all the primes
    // that we have already found.
    for(; result.size() &lt;= primeRequired; next += inc, inc  = 6 - inc) {
        if (isPrime(next, result)) {
            result.emplace_back(next);
        }   
    }   

    // Print out the primes we have found
    for(auto val: result) {
        std::cout &lt;&lt; val &lt;&lt; " ";
    }   
    std::cout &lt;&lt; "\n";
}
When you find a prime number, say 7, you begin crossing out all odd multiples of 7 from the primeCandidates vector.  You do this by incrementing index += loop, where loop is the prime number, and but primeCandidates only holds odd candidates, so the step size in natural numbers would be 2*loop.

The issue is you start by removing 7 from primeCandidates, then 21, then 35.  At this point in the sieve, you've already eliminated multiples of 3 and 5, so marking off 3*7=21 and 5*7=35 is just busy work.  And marking off 1*7=7 is just pointless.  What you should be doing is starting to eliminate at 7*7=49.  It saves only three eliminations during the 7 loop, but the saving get more substantial as the prime gets larger.  For instance, when you get to 199, you wouldn't eliminate 1*199, 3*199, 5*199, 7*199, ... 191*199, 193*199, 195*199, 197*199.  You would just start at 199*199 and go up from there.

Code change:

// Now strain out all factors of the prime we just found, starting with prime^2
index = loop * loop / 2




std::vector&lt;std::size_t&gt; is overkill for primeCandidates.  You only ever store 1 or 0, so allocating 4 or 8 bytes for each candidate is wasting memory.

std::vector&lt;char&gt; would reduce the memory load to 1 byte per candidate.

std::bitset&lt;N&gt; will reduce this to 1 bit per candidate.  Alternately, the vector specialization std::vector&lt;bool&gt; will also give 1 bit per candidate, with a non-compile-time fixed number of bits.