ParallelPrime
This example is a parallel version of the Sieve of Eratosthenes, which finds prime numbers, written using parallel_reduce. This program computes prime numbers up to n. The algorithm here is a fairly efficient version of the Sieve of Eratosthenes, even though the Sieve is not the most efficient way to find primes. Figure 11-5 shows how the Sieve of Eratosthenes finds primes through an elimination process.
The parallel version demonstrates how to use parallel_reduce, and in particular, how to exploit lazy splitting.

Figure 11-5. Finding primes via the Sieve of Eratosthenes
For comparison purposes, let’s look at a serial version of the Sieve in Example 11-21.
Tip
Aha! Parallel and serial versions of code differ in the middle, and clever coding can have a shared driver and can share low-level routines, leaving only a little code different.
Example 11-21. Serial version of count primes
//! Count number of primes between 0 and n
/** This is the serial version. */
Number SerialCountPrimes( Number n ) {
// Two is special case
Number count = n>=2;
if( n>=3 ) {
Multiples multiples(n);
count += multiples.n_factor;
if( PrintPrimes )
printf("---\n");
Number window_size = multiples.m;
for( Number j=multiples.m; j<=n; j+=window_size ) {
if( j+window_size>n+1 )
window_size = n+1-j;
count += multiples.find_primes_in_window( j, window_size );
}
}
return count;
}The equivalent code to do this ...