Notes on Euler Problem 3
Here are my notes on the third Project Euler problem. The problem is "What is the largest prime factor of the number 600,851,475,143?"
Once again, this is a problem that is best solved creating some simple LINQ queries. From the outside, this query generates the list of all prime factors in the very large number:
long largeNumber = 600851475143;
var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber)
orderby p descending
select p;
foreach (var f in allPrimeFactors)
Console.WriteLine(f);
As with the other first two problems, the query is fairly simple. Just grab the prime factors, and order them in descending order.
The work is in the Primes class. This class uses tail recursion to find all prime factors. It starts with the smallest prime number (2), and removes all copies of that number as a factor. Once all those are returned, it will look at the next larger factor and remove those.
A couple quick notes:
1. The algorithm, as written, must start with the smallest prime number. Otherwise, it will find non-prime factors.
2. It doesn't matter that MorePrimeFactors looks at possible factors that aren't prime. They won't appear because any smaller prime factors have already been removed. (for example, 6 won't appear because any factors of 2 or 3 have already been removed).
public static class Primes
{
// Find all prime factors.
public static IEnumerable<int> PrimeFactors(long number)
{
// Start by removing the lowest prime (2)
return MorePrimeFactors(number, 2);
}
// This recursive method finds all prime factors.
private static IEnumerable<int> MorePrimeFactors(long number, int factor)
{
// Find the next prime factor
while (number % factor != 0)
factor++;
// Return it.
yield return factor;
// look again...
if (number > factor)
// recursively look for this factor again, using Num/factor
// as the new big number
foreach (int factors in MorePrimeFactors(number / factor, factor))
yield return factors;
}
}
Note that the PrimeFactors algorithm is not linq based, but it does rely heavily on custom enumerators.