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+

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's 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's 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();
}
3 January 2009