Intel Threading Building Blocks

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 ...