PrimeFactorize method for int

Question

I have written this PrimeFactorize utility method in C# (using LINQPad) which works fine, but feels like it is a bit slow, I was wondering what might be improved. Also looking for any criticism not related to efficiency to make the code better.

// Generate prime factors for a number, e.g., input 12 returns 2 2 3
public static IEnumerable<int> PrimeFactorize(int number)
{
    if(IntUtils.IsPrime(number))
    {
        yield return number;
    }
    else
    {
        List<int> primes = IntUtils.GetPrimesBetween(2, number);            
        while(!IntUtils.IsPrime(number))
        {
            foreach(var p in primes)
            {
                if(number % p == 0)
                {
                    yield return p;
                    number /= p;
                    break;
                }
            }
        }
        yield return number;
    }
}

---

As a note, the IntUtils.IsPrime and IntUtils.GetPrimesBetween are two other utility methods I wrote. I am including GetPrimesBetween below. IsPrime has already been reviewed and it is quite fast by itself and can be found on GitHub.

public static List<int> GetPrimesBetween(int min, int max)
{
    var primes = new List<int>();
    for(var i = min; i <= max; i++)
    {
        if(IntUtils.IsPrime(i) && i != 1)
        {
            primes.Add(i);
        }
    }
    return primes;
}

---

Here is a test run, along with the execution times:

void Main()
{
    var N = 12;
    for(var i = 1; i <= 10; i++) 
    {
        Console.Write("Run # {0} | Number to factorize: {1}\nResult: ", i, N);
        foreach(var P in IntUtils.PrimeFactorize(N)) 
        {
            Console.Write(P + " ");
        }
        // mix up results a bit
        N += N*3 + i;
        Console.WriteLine("\nTime elapsed since start: {0}", Util.ElapsedTime);
    }
}

Results:

Run # 1 | Number to factorize: 12
Result: 2 2 3 
Time elapsed since start: 00:00:00.0130129
Run # 2 | Number to factorize: 49
Result: 7 7 
Time elapsed since start: 00:00:00.0132697
Run # 3 | Number to factorize: 198
Result: 2 3 3 11 
Time elapsed since start: 00:00:00.0133637
Run # 4 | Number to factorize: 795
Result: 3 5 53 
Time elapsed since start: 00:00:00.0139543
Run # 5 | Number to factorize: 3184
Result: 2 2 2 2 199 
Time elapsed since start: 00:00:00.0183778
Run # 6 | Number to factorize: 12741
Result: 3 31 137 
Time elapsed since start: 00:00:00.0528457
Run # 7 | Number to factorize: 50970
Result: 2 3 5 1699 
Time elapsed since start: 00:00:00.2867861
Run # 8 | Number to factorize: 203887
Result: 31 6577 
Time elapsed since start: 00:00:01.9602979
Run # 9 | Number to factorize: 815556
Result: 2 2 3 7 7 19 73 
Time elapsed since start: 00:00:13.5247897
Run # 10 | Number to factorize: 3262233
Result: 3 13 233 359 
Time elapsed since start: 00:01:35.3379070

As you can see, starting at Run #6 the times start getting a lot longer very quickly, and by Run # 10 it takes over a minute to get the results.

Answer 1

First of all, the PrimeFactorize() does never terminate for number = 1 because the check IntUtils.IsPrime(number) will never return true. The call PrimeFactorize(1) should return an empty list.

To compare the performance of various implementations, I used the following simple test program which computes all prime factors of the numbers up to 10,000. The sum is calculated to prevent the compiler from removing function calls whose result is not used, and to verify that all implementations give the same results.

using System.Diagnostics; // for StopWatch

public static void Main()
{
    Stopwatch stopWatch = Stopwatch.StartNew();
    var sum = 0;
    for(var N = 2; N <= 10000; N++) 
    {
        foreach(var P in IntUtils.PrimeFactorize(N))
        {
            sum += P;
        }
    }
    stopWatch.Stop();
    Console.WriteLine("Sum: {0}, Time: {1} ms", sum, stopWatch.Elapsed.TotalMilliseconds);
}

The tests were done on a MacBook, using Mono.

For your code, the result is

 Sum: 10243046, Time: 2945.7256 ms

Your code creates a list of primes in order to find the lowest factor of the given number, and the GetPrimesBetween() function seems be the performance bottleneck.

The IsPrime() function can be improved slightly. Since divisibility by 2, 3, 5 is checked upfront, the loop can start with i = 7. Inside the loop, divisibility by both i and i+2 is checked, so that the next possible divisor is i+4. Therefore the loop should be

    // iterate with trial division
    int i = 7;
    while (i * i <= n)
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
        i += 4;
    }

This reduces the execution time to

Sum: 10243046, Time: 1193.3498 ms

To improve the PrimeFactorize() function, note that every composite number \$ n \$ necessarily has a factor \$ p \le \sqrt n \$. Also, if a factor is found, you can repeatedly check that factor instead of breaking out of the loop and starting with the first prime again.

This leads to the following implementation:

public static IEnumerable<int> PrimeFactorize(int number)
{
    List<int> primes = IntUtils.GetPrimesBetween(2, (int)Math.Sqrt(number));            
    foreach (var p in primes)
    {
        while (number % p == 0)
        {
            yield return p;
            number /= p;
        }
    }
    // Now either number == 1 or number is a prime:
    if (number > 1) {
        yield return number;
    }
}

which reduces the execution time considerably:

Sum: 10243046, Time: 15.6476 ms

A faster way to determine all prime numbers in a given range are sieving methods. A simple implementation of the sieve of Eratosthenes is (taken from https://codereview.stackexchange.com/a/62158/35991, but as an enumerator):

public static IEnumerable<int>GetPrimesUpto(int number) {
    bool[] isComposite = new bool[number + 1];
    for (int x = 2; x <= number; x++)
    {
        if (!isComposite[x])
        {
            yield return x;
            for (int y = x * x; y <= number; y = y + x)
            {
                isComposite[y] = true;
            }
        }
    }
}

which can then be used as:

public static IEnumerable<int> PrimeFactorize(int number)
{
    var primes = IntUtils.GetPrimesUpto((int)Math.Sqrt(number));            
    foreach(var p in primes)
    {
        while (number % p == 0)
        {
            yield return p;
            number /= p;
        }
    }
    if (number > 1) {
        yield return number;
    }
}

Execution time:

Sum: 10243046, Time: 9.6804 ms

But actually you don't need to compute a list of primes first (and I am essentially repeating the arguments from https://codereview.stackexchange.com/a/64795/35991).

The smallest factor of a number is necessarily a prime. You already divide the number by any factor found, but this means that the lowest factor of the updated number is again a prime. So by repeatedly searching for the lowest factor you'll find all prime factors without doing any extra test for primality.

Again it suffices to check for factors up to the square root of the (remaining) number. After that, number is either equal to one or a prime.

This leads to the following function:

// Generate prime factors for a number, e.g., input 12 returns 2 2 3
public static IEnumerable<int> PrimeFactorize(int number)
{
    // Check divisibility by 2:
    while (number % 2 == 0) {
        yield return 2;
        number /= 2;
    }
    // Check divisibility by 3, 5, 7, ...
    for (var i = 3; i * i <= number; i += 2) {
        while (number % i == 0) {
            yield return i;
            number /= i;
        }
    }
    if (number > 1) {
        yield return number;
    }
}

Execution time:

Sum: 10243046, Time: 2.6631 ms

(C# is not my primary language, but I hope that the code demonstrates the idea.)

Answer 2

My answer was based upon the same idea as Martin R but what his has in efficiency (to choose the next prime factor) mine has it in shortness. (but if I have to choose I prefer his...)

IEnumerable<int> PrimeFactorize (int number)
{
    for (var factor = 2; number > 1; ++factor)
        for (; number % factor == 0; number /= factor)
            yield return factor;
}

Answer 3

If you need to call the function often you could make a prime number sieve for example Sieve of Erathostenes that computes all primes (as large as you would need) for once and is stored in a static array and then check with the array whenever need arises. This will be much much faster than calculating if individual numbers are prime over and over again.