The basic method for building a table of primes loops through odd entries in the table. It calls the IsPrime method for each and saves the result in the table. The IsPrime method simply loops through possible factors that are smaller than the square root of a number and determines whether they divide the number evenly. (Revisit Solution 12. Prime factors, for more details).

The key feature of this method as far as parallelization is concerned is that each step looks at a single entry in the table. This means that each step can proceed without interfering with any of the other steps.

The following code shows how the example solution adapts this method to build a primes table in parallel:

// Use the IsPrime method to make a table of prime numbers.
private int BasicMax;
private bool[] BasicIsPrime;
private bool[] MakePrimesTable(int max)
{
    // Make the array and mark 2 and odd numbers greater than 1 as 
    // prime.
    if (max % 2 == 0) max++;
    BasicIsPrime = new bool[max + 1];
    BasicIsPrime[2] = true;

    int start = 1;
    int stop = (int)(max / 2);
    Parallel.For(start, stop + 1, BasicCheck);

    return BasicIsPrime;
}

The method that will be executed in parallel cannot take a lot of extra parameters, so the code declares some values at the form level so that all instances of the method can use them. The BasicMax value indicates the maximum entry in the table. The BasicIsPrime array will hold the primes table.

The MakePrimesTable method builds the table of primes. Its max parameter indicates the largest value that the method should examine. If max is even, the method increments it so that it is odd. You'll see why shortly.

The method then creates the array and marks 2 and odd numbers greater than 1 as prime, much like the previous solution did.

Next, the method calculates the start and stop values to control a loop through the array's odd entries. It then uses the TPL Parallel.For method to invoke the BasicCheck method the required number of times. The first two arguments to Parallel.For give the bounds that the method should pass into the method given as the third argument. The lower bound is inclusive and the upper bound is exclusive, so they mimic the values in a typical for loop that has the following format:

for (int i = lowerBound; i < upperBound; i++) ...

After the parallel calls return, the method returns the primes table.

The following code shows the BasicCheck method:

private void BasicCheck(int i)
{
    i = 2 * i + 1;
    BasicIsPrime[i] = IsPrime(i);
}

This method takes a looping variable as its single parameter. For example, if the first two parameters passed into Parallel.For are 1 and 100, then the BasicCheck method is called 99 times with the parameter values 1 through 99.

We only want to examine odd-numbered entries in the primes table, however, so the method multiplies the looping value by 2 and adds 1. If the looping values run from 1 to max/2 and max is odd, then the new values run from 3 to max. (That's why the earlier code ensured that the largest index in the array was odd. This way, the final call to BasicCheck examines an index that fits within the array.)

After making the looping value odd, the BasicCheck method simply calls the same IsPrime method that was used by the previous solution to see if the entry is prime.

Note that it is very important that the different calls to BasicCheck don't interfere with each other. Each looks at a different entry in the BasicIsPrime array, so none of them modify a value that another instance of the method might be using simultaneously.

If you understand how the preceding code works, it'll be easier to understand how the remaining pieces of this solution build Eratosthenes and Euler sieves. The following code shows how the program builds its Eratosthenes sieve:

// Make a sieve of Eratosthenes.
private int EratosthenesMax;
private bool[] EratosthenesIsPrime;
private bool[] MakeSieveOfEratosthenes(int max)
{
    // Make the array and mark 2 and odd numbers greater than 1 as 
    // prime.
    if (max % 2 == 0) max++;
    EratosthenesMax = max;
    EratosthenesIsPrime = new bool[max + 1];
    EratosthenesIsPrime[2] = true;
    for (int i = 3; i <= max; i += 2) EratosthenesIsPrime[i] = true;

    // Cross out multiples of odd primes.

    int start = 1;
    int stop = (int)(max / 2);
    Parallel.For(start, stop + 1, EratosthenesCheck);

    return EratosthenesIsPrime;
}

If you compare this method to the MakePrimesTable method, you'll find them practically identical. The difference is that this method calls the following EratosthenesCheck method in parallel:

private void EratosthenesCheck(int i)
{
    i = 2 * i + 1;

    // See if i is prime.
    if (EratosthenesIsPrime[i])
    {
        // Knock out multiples of i.
        for (int j = i * 2; j <= EratosthenesMax; j += i)
            EratosthenesIsPrime[j] = false;
    }
}

This method converts the looping value to an odd index, like the BasicCheck method did. It then checks the EratosthenesIsPrime table to see if the corresponding entry is still marked as prime. If the entry is prime, the code marks multiples of the entry as not prime.

Notice that this method is using entries in the table other than entry i, so we should wonder whether the different instances of the EratosthenesCheck method might interfere with each other.

For example, suppose one instance of the method has discovered that 13 is prime, and so marks 23, 36, and other multiples of 13 as nonprime. Now, suppose that this instance of the method has marked 36 as nonprime, and then another instance of EratosthenesCheck examines entry 48. This value is not yet marked as nonprime, so the new instance (incorrectly) thinks that it is prime and marks 96, 144, 192, and other multiples of 48 as nonprime.

Later, the first instance of the method resumes and continues marking multiples of 13 as nonprime. Some of that effort is wasted because the second instance of the method already marked some of those values as nonprime, but the two instances are both trying to write the same value false into the table so it doesn't matter which one executes first.

In contrast, suppose two parallel methods try to read and update the same variable at the same time, assigning it two different values. Depending on the exact timing of the reads and writes, each method might see a different initial value for the variable. The variable will also have a different final value depending on which method executes second.

This solution doesn't have those problems for two reasons. First, a method might see an incorrect value in the table because it has not yet been updated by another instance of the method. If that happens, however, the second instance may do some unnecessary work, but it won't add any incorrect values to the table.

The second reason this program avoids possible problems is that all instances of the method mark table entries with the same value, false. If two instances try to update an array position at the same time, they both write false into the position so there is no race condition.

The program's MakeEulersSieve method is similar to the MakeSieveOfEratosthenes and MakePrimesTable methods shown earlier, except it launches parallel instances of the following EulerCheck method:

private void EulerCheck(int i)
{
    i = 2 * i + 1;
    if (EulerIsPrime[i])
    {
        // Knock out multiples of p.
        int maxQ = EulerMax / i;
        if (maxQ % 2 == 0) maxQ--;    // Make it odd.
        for (int q = maxQ; q >= i; q -= 2)
        {
            // Only use q if it is prime.
            if (EulerIsPrime[q]) EulerIsPrime[i * q] = false;
        }
    }
}

Like the EratosthenesCheck method, this code checks whether entry i is still marked as prime. If it is, the method marks multiples of i as not prime. This time, however, the method only considers multiples of i * q, where q is still marked as prime in the EulerIsPrime array.

There may be some values of q that are still marked as prime, but that will later be marked as nonprime. In that case, the method will mark those multiples as nonprime, even though they will be marked as nonprime again later. As was the case with the EratosthenesCheck method, this method might mark some values as nonprime multiple times unnecessarily, but that will not cause any real problems.

The following screenshots show the PrimesTable and ParallelPrimesTable example solutions:

If you look at the times in the screenshots, you'll see that the parallel version builds its basic table much more quickly. It builds its Eratosthenes sieve slightly faster and its Euler sieve slightly slower. The latter two sieves are so fast to begin with that performing operations in parallel doesn't save much time and adds a bit of overhead. Download the ParallelPrimesTable example solution to see additional details.