.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.