12. Prime table
The obvious approach is to loop through all of the values in the array and call the IsPrime method, described in the previous solution, to see which values are prime. The following method uses this approach:
// Use the IsPrime method to make a table of prime numbers.
private bool[] MakePrimesTable(int max)
{
// Make the array and mark 2 and odd numbers greater than 1 as
// prime.
bool[] isPrime = new bool[max + 1];
isPrime[2] = true;
for (int i = 3; i <= max; i += 2) isPrime[i] = IsPrime(i);
return isPrime;
}
This method allocates an array big enough to hold all of the desired values. It then sets isPrime[2] = true because 2 is prime. It leaves the other even values alone because they are set to false when the array is allocated.
The code then loops through the array's odd numbers and calls the IsPrime method, described in the preceding solution, to set each value's array entry. The method finishes by returning the array.
This method is easy to understand, but it's fairly slow. The IsPrime method loops over many values, so putting calls to IsPrime inside another loop makes the method slow.
While describing the IsPrime method in the preceding solution, I mentioned that we could skip multiples of 2 because, if 2 does not divide evenly into a number, then multiples of 2 cannot either.
We can generalize this rule to make building the table of primes faster. After we consider a prime number p, we know that all multiples of p greater than p are non-prime. For example, we know that 2 is prime, so we can conclude that the multiples 2 × 2, 2 × 3, 2 × 4, ... are not prime.
This leads to the Sieve of Eratosthenes, named after the Greek mathematician Eratosthenes of Cyrene, who discovered it. The idea is to start with a table that contains an entry for all of the numbers of interest. Initially, we assume that all of the numbers are prime.
Now, you start at entry 2 and cross out the later multiples of 2 to indicate that they are not prime.
You then move from 2 to the next entry that is still marked prime, in this case 3, and you cross out the later multiples of 3.
Again, you move to the next numbers that is still marked as prime. The value 4 was crossed out when we considered multiples of 2. The next prime number is 5, so you cross out later multiples of 5.
You continue these steps, finding the next prime number and crossing out its later multiples, until you have considered all of the values in the table.
The following code implements this method:
// Make a sieve of Eratosthenes.
private bool[] MakeSieveOfEratosthenes(int max)
{
// Make the array and mark 2 and odd numbers greater than 1 as
// prime.
bool[] isPrime = new bool[max + 1];
isPrime[2] = true;
for (int i = 3; i <= max; i += 2) isPrime[i] = true;
// Cross out multiples of odd primes.
for (int i = 3; i <= max; i++)
{
// See if i is prime.
if (isPrime[i])
{
// Knock out multiples of i.
for (int j = i * 2; j <= max; j += i)
isPrime[j] = false;
}
}
return isPrime;
}
When the method allocates the isPrime array, its entries are initially false. The code marks 2 and the odd numbers as prime, and leaves the remaining even numbers flagged as non-prime.
Next, the code loops through the odd numbers. If a number is marked as prime, the code marks all of its later multiples as non-prime.
This method is much faster than the previous one, which checked each number individually to see if it was prime. The Sieve of Eratosthenes remained state-of-the art for almost 2,000 years until the 18th century when Euler (pronounced oiler) discovered a major improvement. Euler noticed that you don't need to cross out all multiples of a prime, p; you only need to cross out multiples p × q where q ≥ p and q is also prime.
For example, when you're crossing out multiples of 7, you cross out 7 × 7, 11 × 7, 13 × 7, 17 × 7, and so forth. You already crossed out multiples of smaller primes when you considered them. For example, you crossed out 5 × 7 when you considered multiples of 5.
Also, you already considered non-prime numbers, q, that are bigger than 7 when you considered the prime factors of those numbers. For example, you crossed out 21 × 7 when you examined multiples of 3.
That's the basic improvement on Eratosthenes' algorithm. When you consider a new prime p, you cross out p times larger values in the table that are still marked as prime.
There's one implementation trick here. When you consider multiples of p, you cannot immediately cross them out because you may need them later. For example, suppose you're considering multiples of 3. You start by crossing out the value 3 × 3 = 9.
The next values of q that you consider are 5 and 7. They're still marked as prime, so you cross out 3 × 5 = 15 and 3 × 7 = 21.
The next value of q that you consider is 9. Unfortunately you just crossed out 9 a little while ago, so it's no longer marked as prime. That means you won't cross out 3 × 9 = 27, and that's a problem because 27 is not prime.
The way Euler handled this was to initially mark multiples of 3 as ready for crossing out, but to leave them in the table until after marking all of the multiples of 3. In this example, the program would mark 9 but not cross it out until after it checked the other multiples including 3 × 9 = 27.
The solution shown here handles this problem in a different way by examining multiples of 3 in decreasing order that lets it consider consider 3 × 9 before it considers 3 × 3.
The following code shows the method that builds Euler's sieve:
// Make Euler's sieve.
private bool[] MakeEulersSieve(int max)
{
// Make the array and mark 2 and odd numbers greater than 1 as
// prime.
bool[] isPrime = new bool[max + 1];
isPrime[2] = true;
for (int i = 3; i <= max; i += 2) isPrime[i] = true;
// Cross out multiples of the primes.
for (int i = 3; i <= max; i += 2)
{
// See if i is prime.
if (isPrime[i])
{
// Knock out multiples of p.
int maxQ = max / 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 (isPrime[q]) isPrime[i * q] = false;
}
}
}
return isPrime;
}
This method allocates the isPrime array and marks 2 and the odd numbers as prime. It then loops through the odd numbers, looking for those that are still marked as prime.
When it finds a number p that is marked as prime, the code sets the maxQ variable to the largest odd number, q, where p × q is within the table. For example, suppose i is 19 and max is 1,000. Then the program sets maxQ to 51 because 19 × 51 = 969 is the largest odd multiple of 19 that is less than or equal to 1,000.
The program then loops backwards over odd numbers between maxQ and i. If one of those numbers is still marked as prime, the program crosses out that value times i.
The following screenshot shows the example program building prime tables program by using the three methods described here. The Sieve of Eratosthenes is much faster than the brute-force approach, but Euler's sieve is even faster:
Download the PrimesTable example solution to see additional details.