Wicked Strategery

Project Euler's third problem is solved using LINQ (like the first was).

We'll need a few helper methods - the provide some support for the use of the BigInteger class.

            private static BigInteger GetAnswerToProblem3()
            {
                return Mathematics.PrimeFactorization(600851475143)
                                  .Max();
            }
          

In order to get the prime factorization, I need prime numbers. I created an unbound, on-demand iterator that will generate them. As well as an extension method to check if a BigInteger is prime.

The extension method that determines if a BigInteger is prime makes use of some caching since the larger numbers will become expensive to check.

            public static class BigIntegerExtensionMethods
            {
                #region IsPrime

                private static readonly Dictionary<BigInteger, bool> _isPrimeLookup = new Dictionary<BigInteger, bool>();

                /// <summary>
                /// Determines whether a number is prime or not.
                /// </summary>
                /// <param name="number">The number to check.</param>
                /// <returns>True, if the number is prime.  Otherwise, false.</returns>
                public static bool IsPrime(this BigInteger number)
                {
                    if (number > 2 && number.IsEven)
                    {
                        return false;
                    }

                    bool result;
                    if (!_isPrimeLookup.TryGetValue(number, out result))
                    {
                        result = IsPrimeCoreBruteForce(number);
                        _isPrimeLookup.Add(number, result);
                    }
                    return result;
                }

                private static bool IsPrimeCoreBruteForce(BigInteger number)
                {
                    bool result = true;
                    BigInteger limit = number.Sqrt() + 1; // Upper bound is the sqrt of the number + 1 (for a little bump to ensure the sqrt is included in the check).
                    for (BigInteger x = 3; x < limit; x += 2)
                    {
                        if (number.IsEvenlyDivisible(x))
                        {
                            result = false;
                            break;
                        }
                    }
                    return result;
                }

                #endregion
            }
          

And now the unbound sequence of primes.

            public static class Numbers
            {
                /// <summary>
                /// Gets an infinite sequence that contains prime numbers.
                /// </summary>
                public static IEnumerable<BigInteger> Primes
                {
                    get
                    {
                        BigInteger current = new BigInteger(2);
                        while (true)
                        {
                            if (current.IsPrime())
                            {
                                yield return current;
                            }
                            current++;
                        }
                    }
                }
            }
          

And lastly the method that calculates the prime factorization of a number, called from line 3 of the solution.

            public static class Mathematics
            {
                /// <summary>
                /// Gets the prime factors for a number.
                /// </summary>
                public static IEnumerable<BigInteger> PrimeFactorization(BigInteger number)
                {
                    BigInteger count = BigInteger.Zero;
                    BigInteger current = number;

                    if (number == BigInteger.One)
                    {
                        yield return BigInteger.One;
                        yield break;
                    }

                    while (current > BigInteger.One)
                    {
                        foreach (long p in Numbers.Primes.TakeWhile(bi => bi < number))
                        {
                            if (current % p == 0)
                            {
                                current /= p;
                                count++;
                                yield return p;
                            }
                            if (current == BigInteger.One)
                            {
                                break;
                            }
                        }
                    }
                }
            }