Prime factorization using Linq

For example, 504 = 2 * 2 * 2 * 3 * 3 * 7, let’s assume source = 504:

First, we can find out the first prime factor, by keep increasing a number i from 2 and trying to see if source can be divided by it.

Enumerable.Range(2, source - 1).First(i => source % i == 0);

Then we can find the first prime factor for the remainder, and keep doing it until the remainder is 1. I’m utilizing C# iterator here:

public static IEnumerable<int> GetPrimeFactors(int source)
{
    while (source > 1)
    {
        var first = Enumerable.Range(2, source - 1).First(i => source % i == 0);
        yield return first;
        source = source / first;
    }
}

A lot of times we want to show the result in a shorter way, for example, 504 = 2^3 * 3^2 * 7. This is easy because we can just group the numbers from our previous result:

public static IEnumerable<KeyValuePair<int, int>> GetPrimeFactorsInGroups(int source)
{
    return from f in GetPrimeFactors(source)
           group f by f into g
           select new KeyValuePair<int, int>(g.Key, g.Count());
}

Let’s make a function to print the above example:

public static void PrintPrimeFactors(int source)
{
    var result = String.Join(" * ", from g in GetPrimeFactorsInGroups(source)
                                    select g.Value > 1 ? String.Format("{0} ^ {1}", g.Key, g.Value)
                                                       : g.Key.ToString())

    Console.WriteLine("{0} = {1}", source, result);
}

The output of PrintPrimeFactors(504):

504 = 2 ^ 3 * 3 ^ 2 * 7