Title: Use the Sieve of Eratosthenes to find prime numbers in C#

To use the Sieve of Eratosthenes, you start with a table (array) containing one entry for the numbers in a range between 2 to some maximum value. This table keeps track of numbers that are prime. Initially every number is marked as prime.

Next you look through the values in the table. If the next entry is still marked as prime, then it really is prime and you cross out all of the multiples of that number that appear later in the table.

For example, you initially consider entry number 2. That value is still marked as prime (all of them are so far), so you cross out the multiples or two later in the table.

Next you move to the value 3. It isn't a multiple of 2, so it's still prime. You cross out all of the multiples of 3 later in the table.

Next you move to the value 4. It was crossed out when you examined multiples of 2, so you don't do anything for this value.

You continue moving through the table crossing out multiples of primes.

Note that you only need to consider numbers that are still marked as prime because you have already crossed out any numbers that are factors of a non-prime. For example, suppose you are considering the number 15. It was crossed out when you considered the number 3, so it will already be shown as non-prime in the table. At this point there's no need to consider multiples of 15 later in the table because they were also crossed out when you considered the number 3 because they are also multiples of 3. (They were also crossed out again as multiples of 5.)

The following code shows how the example program builds a Sieve of Eratosthenes.

// Build a Sieve of Eratosthenes. 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 i = 3; i <= max; i += 2) { // See if i is prime. if (is_prime[i]) { // Knock out multiples of i. for (int j = i * 3; j <= max; j += i) is_prime[j] = false; } } return is_prime; }

The code first builds an array big enough to hold the desired numbers. It sets the entries for 2 and the odd numbers to true to indicate that they are prime.

The code then starts at the value 3 and loops through the array, "crossing out" multiples of the primes. (It skips 2 because the even numbers are already marked as non-prime.)

The following code shows how the program uses the MakeSieve method.

// Make a sieve and display the primes. private void btnFindPrimes_Click(object sender, EventArgs e) { lstPrimes.Items.Clear(); lblEstPrimes.Text = ""; lblActualPrimes.Text = ""; Cursor = Cursors.WaitCursor; Refresh(); // Make the sieve. int max = int.Parse(txtMaxNumber.Text); bool[] is_prime = MakeSieve(max); // Display the primes. int num_primes = 0; for (int i = 2; i <= max; i++) if (is_prime[i]) { if (num_primes <= 10000) lstPrimes.Items.Add(i); num_primes++; } if (num_primes > 10000) lstPrimes.Items.Add("..."); // Display the estimated and actual number of primes. lblActualPrimes.Text = num_primes.ToString(); // Display a Legendre estimate ?(n) = n/(log(n) - 1.08366). // See http://mathworld.wolfram.com/PrimeCountingFunction.html. double est = (max / (Math.Log(max) - 1.08366)); lblEstPrimes.Text = est.ToString("0"); Cursor = Cursors.Default; }

This code clears the form's controls and parses the maximum number the user entered. It calls MakeSieve and then loops through the array adding the entries that are marked as prime to the ListBox (up to 10,000 of them).

The code then displays the actual number of primes and a Legendre estimate of the number of primes. For large values of max, the estimate is pretty good.

(As an exercise, see if you can figure out how to avoid allocating room for the even numbers in the array. Then ask yourself if it's worth the effort.)

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