.NET 2.0+

Calculating Prime Factors in C# (2)

The prime factors of a number are all of the prime numbers that can be divided into the number without a remainder. In this article, we will create a method that uses direct search factorisation to generate the list of prime factors for a given value.

Eratosthenes Class

The implementation of the Sieve of Eratosthenes that was described in a previous article generates a list of all of the prime numbers within a given range of values. For this article's implementation we will create a class that performs this calculation. However, rather than generating all of the prime numbers within a range, we will only calculate a new prime number when we require one. We will also retain a list of the previously calculated primes so that they will never need to be recalculated.

To begin, create a new console application and add a class named "Eratosthenes". This class will perform the on-demand prime number calculation. In order for it to operate efficiently, it will hold a collection of currently known prime numbers and an integer variable containing the last number checked. As the first prime number is two, to simplify the process we will add two to the list and set the last checked value to two within the class' constructor.

To add the state variables and the constructor, modify the Eratosthenes class as follows:

public class Eratosthenes : IEnumerable<int>
{
    private static List<int> _primes = new List<int>();
    private int _lastChecked;

    public Eratosthenes()
    {
        _primes.Add(2);
        _lastChecked = 2;
    }
}

Note that the class implements the generic IEnumerable interface. This is because we are going to create an iterator that permits us to loop through the prime numbers as if they were held in a collection. As such, we will be using the System.Collections namespace so add the following directive at the top of the code file:

using System.Collections;

When we test to see if values are prime, we will always be working in ascending numerical order and testing all values. This means that we can use the prime numbers from the list that are already known and the Sieve of Eratosthenes process from the previous article to check if the next number is prime.

Add the following method to the Eratosthenes class for the prime test. This method is almost identical to the one from the earlier article.

private bool IsPrime(int checkValue)
{
    bool isPrime = true;

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

    return isPrime;
}

The actual generation of prime numbers will occur within the class' iterator. When the GetEnumerator method is called, either directly or due to the execution of a foreach loop, a two-stage process will occur. Firstly, each of the existing values in the prime number list will be returned using the yield command. Once this list is exhausted, new prime numbers will be calculated, added to the list for future use and returned using a second yield statement. This will continue until the maximum integer value is reached or until no further prime numbers are requested.

To add the iterator function, add the following code to the class:

public IEnumerator<int> GetEnumerator()
{
    foreach (int prime in _primes)
    {
        yield return prime;
    }

    while (_lastChecked < int.MaxValue)
    {
        _lastChecked++;

        if (IsPrime(_lastChecked))
        {
            _primes.Add(_lastChecked);
            yield return _lastChecked;
        }
    }
}

In order to fully support the IEnumerable<int> interface, we must implement the non-generic IEnumerable interface too. This requires a single method to be added to the Eratosthenes class:

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}