Finding the largest prime factor of a number
This is another classic problem at Project Euler that can be solved with the old trick of top down programming, like so:
PrimeFactors(number).DefaultIfEmpty(number).Max();
It's a nice solution, supposing PrimeFactors() actually returns all prime factors of any given number. But before getting there, it's a good idea to discuss what DefaultIfEmpty() is doing there. The thing is that somebody could make this innocent call: PrimeFactors(1), which of course returns an empty collection, which in turn makes PrimeFactors(1).Max() throw an exception (trying to get the maximum out of nothing, eh?) DefaultIfEmpty(x) to the rescue: when DefaultIfEmpty(x) is applied to a "reasonable" collection it returns it untouched, but when it's applied to an empty collection it returns a new collection with just un item: x. So, in our case, PrimeFactors(1).DefaultIfEmpty(1).Max() is just a looooong alias for 1. DefaultIfEmpty() is very useful for those special cases with empty collections.
With that behind, let's see how we get all the prime factors of a number:
1 IEnumerable<ulong> PrimeFactors(ulong number)
2 {
3 Func<ulong, ulong> FindDivisor = n => n == 1UL ? 1UL : CandidateFactors(n).First(c => n % c == 0);
4
5 var factors = new HashSet<ulong>();
6 while (number > 1UL)
7 {
8 ulong divisor = FindDivisor(number);
9 factors.Add(divisor);
10 number /= divisor;
11 }
12
13 return factors;
14 }
At line 3 we define a function (we are using lambdas just for fun) that finds a divisor for a number, for example FindDivisor(45) returns 3 and FindDivisor(49) returns 7. The workhorse is the while loop starting on line 6, it starts with a number, let's say 45, find the divisor 3, saves it in factors and goes on with 15 (45 / 3), now it finds a divisor for 15, in this case 3 again, saves it in factors and goes on with the 5 (15 / 3), and so on and so on until all is left is a 1. Meanwhile factors has been accumulating 3, 5, etc.: the prime factors of the original number. An interesting detail is that factors is a set, so it doesn't have any duplicates.
Finally let's check the CandidateFactors() definition:
1 IEnumerable<ulong> CandidateFactors(ulong n)
2 {
3 yield return 2UL;
4 for (ulong candidate = 3UL; candidate <= n; candidate += 2UL)
5 yield return candidate;
6 }
As you can see, this function simply produces the sequence 2, 3, 5, 7, 9, ..., n which are the possible divisors of n. You can think of a more clever implementation, one that produces a less indiscriminate list of candidates, but let's leave that for another day.
And in this way, this mixture of LINQ (DefaultIsEmpty(), Max(), First()), lambdas (FindDivisor), iterators (yield) and good old imperative programming, leads us to a compact and effective solution to an old problem. Do you happen to have a more elegant solution?