Title: Use Euler's Sieve to find prime numbers in C#

The Sieve of Eratosthenes is a simple way to make a list of prime numbers. The basic idea is to make an array of numbers. Starting with 2, cross out all multiples of 2 greater than 2. Next cross out all of the multiples of 3 greater than 3, and so forth.

More generally, find the next number on the list that is not yet crossed out (in this example, 5 would be next) and cross out its multiples after the first one. See the post Use the Sieve of Eratosthenes to find prime numbers in C# for an implementation.

Euler noticed an improvement. When you are considering the multiples of the next prime p, you only need to consider numbers p * q where q >= p and q is prime.

For example, when you consider multiples of 7, you would mark 7 * 7, 7 * 11, 7 * 13, and so forth as non-prime. Here q is 7, 11, 13, and so forth.

Values where q is smaller than 7 were already crossed out when you crossed out multiples of the smaller values. For example, when you crossed out multiples of 5, you crossed out 5 * 7.

Non-prime numbers q bigger than 7 were considered when the factors of those numbers were considered. For example, you crossed out 7 * 21 when you examined multiples of 3.

There's one implementation trick here. When you consider multiples of p, you cannot immediately remove them from the list 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 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 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 don't cross out 3 * 9 = 27. That's a problem because 27 is not prime.

The way the original Euler's sieve method handles this is it initially marks the multiples of 3 as ready for crossing out, but it doesn't actually cross them out until it has marked them all. In this example, the program would mark 9 but not cross it out until after it checked the other multiples including 3 * 9 = 27.

This example program handles this somewhat differently. It examines the multiples of 3 in decreasing order. That way it considers 3 * 9 before it considers 3 * 3.

The following code shows how this example builds Euler's sieve.

// Build Euler's Sieve. private bool[] MakeSieve(int max) { // Make an array indicating whether numbers are prime. bool[] is_prime = new bool[max + 1]; is_prime[2] = true; for (int i = 3; i <= max; i += 2) is_prime[i] = true; // Cross out multiples of odd primes. for (int p = 3; p <= max; p += 2) { // See if i is prime. if (is_prime[p]) { // Knock out multiples of p. int max_q = max / p; if (max_q % 2 == 0) max_q--; // Make it odd. for (int q = max_q; q >= p; q -= 2) { // Only use q if it is prime. if (is_prime[q]) is_prime[p * q] = false; } } } return is_prime; }

The code starts by creating and initializing an is_prime array as in the previous example.

It then makes p loop over the odd numbers between 3 and max. If p is still marked as prime, the program must cross out its multiples.

In that case, the code calculates the largest multiple that it must consider. It then makes q loop from that value down to p. (It checks only odd values for q because even multiples of p are already marked as non-prime. All of the even numbers are.) If q is still marked as prime, the code crosses out p * q.

The rest of the program is similar to the previous example. See that example for information about how the program displays results, including how it estimates the number of primes.

So does all this extra complication make the program any faster? Yes it does. In one test, the previous example took roughly 0.36 seconds to build a sieve for 10,000,000 numbers. It took this example, only about 0.16 seconds.

Download the example to experiment with it and to see additional details.