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

Sieve of Eratosthenes

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];
    for (int i = 2; i <= max; i++) is_prime[i] = true;

    // Cross out multiples.
    for (int i = 2; i <= max; i++)
    {
        // See if i is prime.
        if (is_prime[i])
        {
            // Knock out multiples of i.
            for (int j = i * 2; 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 in the array to true to indicate that all of the numbers are prime. (It skips the values 0 and 1 because technically they are not prime.)

The code then starts at the value 2 and loops through the array, “crossing out” multiples of the primes.
As an exercise, see if you can figure out a more efficient way to handle even numbers.

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();
    int max = int.Parse(txtMaxNumber.Text) + 1;
    bool[] is_prime = MakeSieve(max);
    for (int i = 2; i < max; i++)
        if (is_prime[i]) lstPrimes.Items.Add(i);
}

This code clears the program’s ListBox 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.

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 Example   Follow me on Twitter   RSS feed


This entry was posted in algorithms, mathematics and tagged , , , , , , , , , . Bookmark the permalink.

One Response to Use the Sieve of Eratosthenes to find prime numbers in C#

  1. Pingback: Use Euler's Sieve to find prime numbers in C# -

Leave a Reply

Your email address will not be published. Required fields are marked *