.NET 2.0+

Prime Numbers - Sieve of Eratosthenes (2)

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.

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.