BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 2.0+

Prime Numbers - Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm that can be used to find the series of prime numbers. The algorithm is a manual one, requiring a grid of numbers that can be highlighted as primes are found and struck off when not prime.

Prime Numbers

A prime number is a natural number that can only be divided by two integers without remainder. The two divisors are always one and the prime number itself. The number one is no longer considered a prime number as it has only one integer divisor. The first five prime numbers are 2, 3, 5, 7 and 11.

Prime numbers have many practical uses in mathematics and data security. However, generating prime numbers, particularly large ones, is not a simple task. One of the simplest algorithms for creating a list of prime numbers is the Sieve of Eratosthenes.

The Sieve of Eratosthenes

The Sieve of Eratosthenes algorithm uses a repetitive, manual process to determine a series of prime numbers. The algorithm requires that all of the numbers between two and the highest value to be tested are written down. A recursive process is then followed. Firstly the first number not deleted from the list or already highlighted is circled. This is a prime number. Secondly, all of the numbers remaining that can be divided by the new prime number are deleted from the list. This is repeated until the list contains only circled items. The process is then complete and all of the circled numbers are known to be primes.

Adapting the Algorithm

The Sieve of Eratosthenes is an interesting algorithm but is not perfectly suited to computerisation. However, the principles of the algorithm can be adapted to create a program that generates the same list of prime numbers. This is the goal of this article.

The prime number generator program will be a simple console application developed in C#. To begin, create a new console application named "Eratosthenes".

Storing the Prime Numbers

As the program executes, the prime numbers will be outputted to the console and stored within a collection. For simplicity, we will use a simple generic list containing 64-bit integers. To create this list, add the following class-scoped variable declaration. NB: If you wish to develop this program using .NET 1.1, use an ArrayList for the collection.

private static List<long> _primes = new List<long>();

Adding the First Prime Number

The first prime number by definition is two. This is also the only even prime; all other prime numbers are odd. To take advantage of this, when the prime number generation process is in progress, we will only check odd numbers. This means that it makes the program simpler if we add the number two manually when the program starts. to do this, add the following lines of code to the Main method:

_primes.Add(2);
Console.Write(2);

Creating the Main Loop

In the Sieve algorithm, when each prime number is identified, all other numbers that have it as a factor are erased from the list. Rather than create a very large list of numbers and remove them as their divisors are determined to be prime, we will reverse the process. We will loop through all of the odd numbers and in each case check if the value is prime, using the collection of previously found prime numbers as potential divisors.

As we have already removed the necessity to check the number two, the testing can begin at the number three and increase by two each time so that only odd numbers are considered. We can therefore create a for loop for the main part of the program, which loops from 3 to the largest available long integer. To create the main loop, add the following to the Main method:

for (long checkValue = 3; checkValue <= long.MaxValue; checkValue += 2)
{
    if (IsPrime(checkValue))
    {
        _primes.Add(checkValue);
        Console.Write("\t{0}", checkValue);
    }
}

This loop uses a yet undefined method, named "IsPrime", to check if the value is prime. If it is, the new prime number is outputted to the console and added to the list of prime numbers.

The IsPrime Method

The final task is to create the method that checks if a number is prime. This method must return a Boolean value that is true if the number is prime and false if it is not. The method is shown below:

private static bool IsPrime(long checkValue)
{
    bool isPrime = true;

    foreach (long prime in _primes)
    {
        if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
        {
            isPrime = false;
            break;
        }
    }

    return isPrime;
}

The process followed is quite simple. Firstly it is assumed that the number passed in the parameter is prime. If it is later determined that it is not, the "isPrime" variable's value will be altered before it is returned to the calling method. Next, all of the prime numbers already identified are looped through in order using a foreach loop. If any of the prime numbers is a divisor of the value being tested, the "isPrime" variable is changed and the loop is stopped. If none of the prime numbers is a divisor, the number must be prime and the method returns true. This is the equivalent of circling a number in the Sieve process.

One additional optimisation is included in the if statement within the loop. The second condition checks if the current prime number is less than or equal to the square root of the value being tested. If the prime number is greater than the square root of the test value then no further checking is required as if the test value was not prime the paired divisor would already have been detected.

Try executing the program to see the prime numbers. You may want to add some pauses in the code so that the numbers do not disappear off the screen too quickly.

24 June 2008