"Largest prime factor" ( https://projecteuler.net/problem=3 )

ProjectEuler-0003.cs

// Also available as a Gist @ http://csharppad.com/gist/f8301db69cb06a2b871fc0511930f54b
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            var valueToSolve = 600851475143;
            //PrimeFactorHelper.WriteToConsole(valueToSolve);
            var primeFactors = PrimeFactorHelper.GetPrimeFactors(valueToSolve);
            Console.WriteLine(string.Format("The largest prime factor of {0} is {1}.", valueToSolve, primeFactors.Max()));
            return;
        }

        public static class PrimeFactorHelper
        {
            public class Item
            {
                public bool IsPrime { get; private set; }
                public BigInteger[] PrimeFactors { get; private set; }

                public Item(bool isPrime, BigInteger[] primeFactors)
                {
                    IsPrime = isPrime;
                    PrimeFactors = primeFactors;
                }

                public Item()
                {
                    IsPrime = false;
                    PrimeFactors = new BigInteger[0];
                }
            }

            public static Dictionary<BigInteger, PrimeFactorHelper.Item> Sequence;

            static PrimeFactorHelper()
            {
                Sequence = new Dictionary<BigInteger, PrimeFactorHelper.Item>();
            }

            public static BigInteger[] GetPrimeFactors(BigInteger value)
            {
                if (value <= 0)
                    throw new NotSupportedException("Only positive integer values greater than 1 are supported in working with the Prime Factors sequence");

                Console.WriteLine(string.Format("Running GetPrimeFactors({0})", value));

                BigInteger[] primeFactors;
                var rangeOfValues = Enumerable.Range(1, (int)GetSqrt(value)).ToList();

                BigInteger maxDivisor = rangeOfValues.SelectMany(x => (value % x == 0) ? new BigInteger[] { x, (value / x) } : new BigInteger[] { x })
                    .Where(x => x != value)
                    .OrderByDescending(x => x)
                    .FirstOrDefault(x => value % x == 0 || x == 1);

                var isPrime = (maxDivisor == value || maxDivisor <= 1);

                if (isPrime)
                {
                    primeFactors = new[] { value };
                }
                else
                {
                    var quotient = value / maxDivisor;
                    var primeFactorsMaxDivisor = GetPrimeFactors(maxDivisor);
                    var primeFactorsQuotient = GetPrimeFactors(quotient);
                    primeFactors = primeFactorsMaxDivisor.Concat(primeFactorsQuotient).Distinct().OrderBy(x => x).ToArray();
                }

                if (!Sequence.ContainsKey(value))
                {
                    Sequence.Add(value, new Item(isPrime, primeFactors));
                }

                return primeFactors;
            }

            public static void WriteToConsole(BigInteger value)
            {
                var primeFactors = PrimeFactorHelper.GetPrimeFactors(value);

                Console.WriteLine(
                    "The prime factor{0} of {1} {2}: {3}",
                    (primeFactors.Length != 1 ? "s" : ""),
                    value,
                    (primeFactors.Length != 1 ? "are" : "is"),
                    string.Join(",", primeFactors)
                );
            }

            public static BigInteger GetSqrt(BigInteger n)
            {
                if (n == 0) return 0;
                if (n > 0)
                {
                    int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));
                    BigInteger root = BigInteger.One << (bitLength / 2);

                    while (!isSqrt(n, root))
                    {
                        root += n / root;
                        root /= 2;
                    }

                    return root;
                }

                throw new ArithmeticException("NaN");
            }

            private static Boolean isSqrt(BigInteger n, BigInteger root)
            {
                BigInteger lowerBound = root * root;
                BigInteger upperBound = (root + 1) * (root + 1);

                return (n >= lowerBound && n < upperBound);
            }
        }
    }
}