.NET 2.0+

Calculating Prime Factors in C#

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.

Prime Factors

The prime factors of an integer value are the prime numbers that the value can be divided by without leaving a remainder. For example, the prime factors of the number fifteen are three and five, as 3 x 5 = 15 and both of these factors are prime. It is possible that the same prime factor may appear twice in a list, such as the prime factors for twelve, which are two, two and three (2 x 2 x 3 = 12). Every positive integer can be expressed as a list of its prime factors and every positive integer has a single, unique set of prime factors.

Prime numbers are particularly useful for cryptography, such as that used for secure Internet connections. When using public / private key encryption schemes for securely exchanging data, the encryption is based upon the product of large prime numbers. This is useful because it is a fast operation to multiply prime numbers but it is difficult, and very time-consuming, to reverse this process and find the original prime factors.

Prime Factorisation Algorithm

To reduce a value to its prime factors we must use a factorisation (US: factorization) algorithm. In this article we will use an algorithm known as direct search factorisation. Although this is not the fastest or most efficient manner of calculating prime factors, it is reasonably simple to implement and to understand.

The direct search factorisation algorithm has the following steps. The process requires that you have a pre-calculated list of prime numbers available:

1. Get the lowest prime number from the prime number list.
2. Check if the prime number divides exactly into the value being factorised.
3. If the number divides without remainder, add the prime number to the list of prime factors and divide the value being factorised by this prime number. Repeat from step 2 using the same prime number.
4. If the value being factorised has been reduced to one, exit the algorithm as the list of prime factors is now complete.
5. Get the next-highest prime number from the list and repeat from step 2.

A key element of this algorithm is the requirement for a list of prime numbers. These can be calculated using a variation upon the Sieve of Eratosthenes algorithm that was described in an earlier article. If you are unaware of this algorithm you should read the article before continuing. The code used will be modified slightly for the prime factorisation algorithm.

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:

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();
}

GetPrimeFactors Method

Now that we have a class that generates a list of prime numbers, we can use it within the direct search factorisation algorithm. To do so, we will create a simple method named "GetPrimeFactors". Add the following method to the Program class of the console application project. The method is defined as a static member as we are going to call it from the Main method. However, there is no reason that this could not be changed to be an instance member for your own programs.

private static IEnumerable<int> GetPrimeFactors(
    int value, Eratosthenes eratosthenes)
{
    List<int> factors = new List<int>();

    foreach (int prime in eratosthenes)
    {
        while (value % prime == 0)
        {
            value /= prime;
            factors.Add(prime);
        }

        if (value == 1)
        {
            break;
        }
    }

    return factors;
}

The GetPrimeFactors method implements all five steps of the algorithm in a simple function. Two parameters are included. The first parameter accepts the value that is to be reduced to a list of prime factors. The second parameter is an Eratosthenes object that will provide the prime numbers.

The first line of the method creates a new list of integers. This will be used to hold the prime factors as they are determined.

The second line starts looping through the list of the prime numbers provided by the Eratosthenes object. This includes the primes that are already known and any that will need to be calculated. The loop will be allowed to continue until all of the prime factors have been identified.

Within the foreach loop is a while loop. This secondary loop tests whether the value being factorised can be divided exactly by the current prime number. If it can, the prime number is added to the factors list and the value is divided accordingly. The while loop will continue to add duplicates of the same prime number to the list until a division without remainder is no longer possible.

The if statement checks if the process is complete. If the value being factorised has reduced to one, the foreach loop is exited and the list of prime factors is returned. If not, execution continues with the next prime number from the Eratosthenes object.

Testing the Algorithm

We can test the algorithm by adding the following code to the Main method. This creates a new prime number generator before requesting the prime factors of one hundred and twenty.

Eratosthenes eratosthenes = new Eratosthenes();

IEnumerable<int> factors = GetPrimeFactors(120, eratosthenes);

foreach (int i in factors)
{
    Console.Write("{0} ", i);   // Outputs "2 2 2 3 5"
}

For a more interactive prime factor generator test, download the project from the link at the top of the article. The sample project allows you to perform multiple requests. Each request uses the same prime number generator so that the prime number list is not recalculated. Note that the time taken to generate the prime factors is dependant upon the size of the largest factor, not the size of the value being factorised. A large prime number takes much longer to factorise than a large number with low-value factors. Values with large prime factors can take a very long time to reduce.