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.

Finding primes via the Sieve of Eratosthenes

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.


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

Get Intel Threading Building Blocks now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.