.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.