Parallel sieve of Eratosthenes For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the multiples of this prime number from the boolean vector (the one that tells whether a number is a prime or not). Here is my code:

#include &lt;cmath&gt;
#include &lt;functional&gt;
#include &lt;thread&gt;
#include &lt;vector&gt;

// Invalidates the multiples of the given integer
// in a given boolen vector
template&lt;typename Integer&gt;
void apply_prime(Integer prime, std::vector&lt;bool&gt;&amp; vec)
{
    for (Integer i = prime*2u ; i &lt; vec.size() ; i += prime)
    {
        vec[i] = false;
    }
}

template&lt;typename Integer&gt;
auto sieve_eratosthenes(Integer n)
    -&gt; std::vector&lt;Integer&gt;
{
    std::vector&lt;bool&gt; is_prime(n, true);
    std::vector&lt;std::thread&gt; threads;
    std::vector&lt;Integer&gt; res;

    auto end = static_cast&lt;Integer&gt;(std::sqrt(n));
    for (Integer i = 2u ; i &lt;= end ; ++i)
    {
        // When a prime is found,
        // * add it to the res vector
        // * spawn a thread to invalidate multiples
        if (is_prime[i])
        {
            res.push_back(i);
            threads.emplace_back(apply_prime&lt;Integer&gt;,
                                 i, std::ref(is_prime));
        }
    }

    for (auto&amp; thr: threads)
    {
        thr.join();
    }

    // Add the remaining primes to the res vector
    for (Integer i = end+1u ; i &lt; is_prime.size() ; ++i)
    {
        if (is_prime[i])
        {
            res.push_back(i);
        }
    }
    return res;
}


The primes are added in two steps to the res vector: every prime \$ p \$ such as \$ p &lt; \sqrt{n} \$ is added when the prime is found, before the corresponding thread is thrown. The other primes are added at the end the of the function. Here is an example main:

int main()
{
    auto primes = sieve_eratosthenes(1000u);

    for (auto prime: primes)
    {
        std::cout &lt;&lt; prime &lt;&lt; " ";
    }
}


I was pretty sure that I would get some problems due to parallelism, but for some reason, it seems to work. I got the expected results in the right order. Just to be sure, I would like to know whether my program is or correct or whether it has some threading issues that I couldn't see.

Note: I used many of the ideas from the answer to improve the code and wrote a follow-up question.
As you are correctly assuming there are multiple threading related issues with your code, but lets tease you and start with the usual suspects.

Naming

The name apply_prime is misleading and inexpressive.
Neither does the function really require a prime nor does apply do it justice.
You should name it something along the lines: strike_out_multiples or something similar.

Efficiency

Your loop can be twice as fast by doing steps of two instead of one.

And now for the main act:

Thread safety

I am no expert here but I can spot at least two problems:

Ordering:

Nothing prevents the system from "favoring" your main thread and letting all others run after the main thread is hitting the join loop. This results in wrong results as the mainthread plowed through the completely true vector before anyone could tell it that for example 4 is not prime.

Parallel writes:

This might be a bit of a corner case and not a problem anymore but at least in the old standard std::vector&lt;bool&gt; was a specialization that used only one bit per value. While this saves you some space it comes with the cost of actually accessing 8 bits when only working on one. This means that two threads might well be working on different bits but in the same byte. Consider this:

Thread 1 writes false to bit 4 while thread 2 writes false to bit 6. Both are located in byte 0. Now both start out with reading the initial value of the byte, say (true, true, true, false, true, true, true, true) and stores them! Now one of the two threads will write its value later than the other and overwrites the false of the other one -> lost update.

Maybe this can even happen with byte sized booleans as some architectures do not allow for only byte-wise access but only word wise (which results in the same problem, only with wider sizes).