13. Prime factors

The most obvious approach to prime factoring a number is to loop through values less than that number and see if they divide into that number evenly. Each time you find such a factor, you divide it from the number. You continue this process until the modified number equals 1.

The following method uses this approach:

// Divide by smaller values up the the square root of the value.
private List<long> Method1(long number)
{
    checked
    {
        List<long> factors = new List<long>();

        // Pull out 2s.
        while (number % 2 == 0)
        {
            factors.Add(2);
            number /= 2;
        }

        // Pull out odd factors.
        long limit = (long)Math.Sqrt(number);
        for (long factor = 3; factor <= limit; factor += 2)
        {
            while (number % factor == 0)
            {
                factors.Add(factor);
                number /= factor;
                limit = (long)Math.Sqrt(number);
            }
        }

        // Add the leftover.
        if (number != 1) factors.Add(number);
        return factors;
    }
}

The method first uses a loop to pull out factors of 2. As long as the number is divisible by 2, the method adds 2 to the list of factors and divides the number by 2.

Next, the code loops over odd values between 3 and the square root of the number. It doesn't need to consider values greater than the number's square root because, if there is a factor p greater than the square root, then there is another factor, q, less than the square root so that p × q equals the number.

When it finds a factor that divides into the number evenly, the code adds it to the factor list, divides the number by the factor, and then updates the square root for the updated number.

When it finishes examining possible factors, the number is either 1, in which case we have found all of the factors, or it is prime. If the number is prime, the code adds it to the factor list.

This method is reasonably efficient if you only want to factor a single value. If you need to factor a large number of values, however, then you can improve performance by making a pre-calculated table of prime numbers.

The preceding method considers all odd numbers as possible factors, but it really only needs to consider prime numbers as factors. If you build Euler's sieve as was described in the preceding solution, then you can use it to decide which numbers might be factors.

The PrimeFactors example solution uses the methods described in the preceding solution to build Euler's sieve. It then uses the following code snippet to convert the sieve into a list containing the prime numbers:

// Convert the sieve into a list of primes.
Primes = new List<long>();
Primes.Add(2);
for (int i = 3; i <= max; i += 2)
    if (!isComposite[i]) Primes.Add(i);

This code creates a list to hold the prime numbers. It then scans through the sieve stored in the isComposite array, adding the primes to the list.

The following method uses the list of prime numbers to factor a value:

// Use a pre-made sieve of primes up to MaxNumber.
// Update the limit when we find a prime.
private List<long> Method2(long number)
{
    checked
    {
        List<long> factors = new List<long>();

        // Pull out primes.
        long limit = (long)Math.Sqrt(number);
        foreach (long prime in Primes)
        {
            while (number % prime == 0)
            {
                factors.Add(prime);
                number /= prime;
                limit = (long)Math.Sqrt(number);
            }
            if (prime > limit) break;
        }

        // Add the leftover.
        if (number != 1) factors.Add(number);
        return factors;
    }
}

This method is similar to the earlier one, except it only considers prime numbers when looking for factors. It sets limit to the square root of the number. It then loops through the precomputed primes list. While a prime evenly divides into the number, the code adds the prime to the factor list, divides the number by the prime, and then updates the limit.

If the prime that the method is considering is greater than the limit, the code breaks out of its loop.

Finally, if the number has not been reduced to 1 by the time the loop ends, the code adds it to the factor list as before.

The following screenshot shows the PrimeFactors example solution factoring the number 12,345,678,901,234:

When you enter a value and click Go, the program uses the two methods described earlier to factor the number. In the preceding screenshot, you can see that the first method took around 0.0009 seconds and the second method too around 0.0002 seconds when using the second method. The second method is considerably faster, although the absolute times are minuscule, so it would only be worth using the second approach if you needed to factor a lot of values. When it started, the program took 1.35 seconds to build a primes list containing numbers up to the square root of 1 × 1015. It can use that list to factor numbers up to 1 × 1015.

Download the PrimeFactors example solution to see additional details.