Return to Revisions

It has already been mentioned in the answers to the previous question, but there are really many places where the code does useless iterations on multiples of 2. Actually, these useless iterations 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 skipped 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 anymore since it's only used in one place (in the sequential sieve).
• 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 other answers that these loops begin at prime*prime, which is always odd. Therefore, 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 prallel 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 should contain: the values below 3u and all the even values are ignored. There ought to be a way to avoid uselessly storing that many values.