Return to Revisions

It has already been mentioned in an answer to the previous question, but there are really many places where the code does useless iterations on multiples of 2. Actually, these useless operations can be removed almost everywhere:

• In the sequential version of the sieve, strike_out_multiples(2u, is_prime); can be removed since the multiples of 2 are not even considered by the algorithm in the last part of the function where the actual prime numbers are added to the vector. Therefore, we don't need strike_out_multiples as a separate function anymore since it's only used once.
• Similarly, first can be declared as std::size_t first = 1u in the parallel version of the algorithm: 0u corresponds to the index of the vector where the prime number 2u is stored.
• There are loops that begin with 2u*prime at several places in the code. It has been proposed in another answer that these loops should begin at prime*prime instead, which is always odd since we ignore 2u. Consequently, the increment of these loops can be changed to n += 2u*prime (instead of n += prime) to ignore the even values.
• The initialization of is_prime in the parallel version of the sieve can begin at the index 3u (the previous ones can be ignored) and have an increment of 2u to skip the even values.

This highlights the fact that the vector is_prime contains twice as many values as it could contain: the values below 3u and all the even values are not used. There ought to be a way to avoid uselessly storing that many values.