Problem 3: What is the largest prime factor of the number 600851475143 ?
With enough extension methods we can make 3 really simple:
600851475143.LargestPrimeFactor()
Where:
public static int LargestPrimeFactor(this long number)
{
return number.PrimeFactors().Last();
}
public static IEnumerable<int> PrimeFactors(this long number)
{
long remainder = number;
while (true)
{
var factor = remainder.SmallestPrimeFactor();
yield return factor;
remainder = remainder / factor;
if (remainder == 1)
{
break;
}
}
}
private static int SmallestPrimeFactor(this long number)
{
var primes = new Eratosthenes();
var factor = primes.FirstOrDefault(x => number.IsDivisbleBy((long)x));
if (factor == 0)
{
throw new Exception(String.Format(“Factor not found! {0}”,number));
}
return factor;
}