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.

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.

3 January 2009