Euler Problem 5
Well, it's time to post another solution and look at how LINQ and C# 3.0 can create elegant code for these problems.
The fifth problem asks you to find the smallest number that is divisible by all the natural numbers from 1 through 20. You can trivially find the answer like this:
1 private
static
void BruteForce()
2 {
3 var divisible = (from n in
Enumerable.Range(1, int.MaxValue)
4 where (n % 2 == 0
5 && n % 3 == 0
6 && n % 4 == 0
7 && n % 5 == 0
8 && n % 6 == 0
9 && n % 7 == 0
10 && n % 8 == 0
11 && n % 9 == 0
12 && n % 10 == 0
13 && n % 11 == 0
14 && n % 12 == 0
15 && n % 13 == 0
16 && n % 14 == 0
17 && n % 15 == 0
18 && n % 16 == 0
19 && n % 17 == 0
20 && n % 18 == 0
21 && n % 19 == 0
22 && n % 20 == 0
23 )
24 select n).First();
25 Console.WriteLine(divisible);
26 }
But don't do that. It's very slow. Let's think a bit about the math, and the answer gets much easier. If you remember middle school math, you are being asked to find the greatest common divisor for all numbers 1-20. The unique factorization theorem is what you need here. It states that every number can be written in exactly one way as the product of prime numbers. The greatest common divisor can be found by multiplying the highest powers of each prime factor. In code, it's a little easier to turn the definition around and peel off prime factors from every number in the list. It's faster and simpler than finding all the prime factors.
You start with a list like this: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1 really doesn't do much, so we'll start with 2. Keep the 2, and replace every number greater than 2 that is divisible by 2 with that number divided by 2:
1, 2, 3, 2, 5, 3, 7, 4, 9, 5
Move to the next number (3). Repeat:
1, 2, 3, 2, 5, 1, 7, 4, 3, 5
Move to the next number (another 2). Repeat:
1, 2, 3, 2, 5, 1, 7, 2, 3, 5
Continue until done:
1, 2, 3, 2, 5, 1, 7, 2, 1, 1
Multiply: 2520
That gives us this algorithm:
1 private
static
void Better()
2 {
3 var numbers = Enumerable.Range(1, 20).ToArray();
4 // remove common factors:
5 for (int index = 0; index < numbers.Length; index++)
6 for (int subIndex = index + 1; subIndex < numbers.Length; subIndex++)
7 if (numbers[subIndex] % numbers[index] == 0)
8 numbers[subIndex] /= numbers[index];
9
10 var answer = numbers.Aggregate(1, (product, number) => product * number);
11
12 Console.WriteLine(answer);
13 }
But you know what. I don't like those loops. I'd rather write methods that operate on a sequence. It's another rather simple example of tail recursion. For any sequence, peel off the first number. Then, return that number followed by the rest of the sequence divided by that first number, where possible. Pipe the remaining sequence back into the same function:
11 private
static
void Best()
12 {
13 var numbers = Enumerable.Range(1, 20);
14
15 var answer = numbers.LeastCommonFactor().Aggregate(1,
16 (product, number) => product * number);
17
18 Console.WriteLine(answer);
19 }
20
21 private
static
IEnumerable<int> LeastCommonFactor(this
IEnumerable<int> list)
22 {
23 // Stop if the list is empty:
24 if (!list.Any())
25 yield
break;
26
27 int factor = list.First();
28 yield
return factor;
29
30 var remaining = from item in list.Skip(1)
31 select (item % factor == 0) ? item / factor : item;
32 foreach (int item in remaining.LeastCommonFactor())
33 yield
return item;
34 }
Now that's a simple, elegant algorithm. And, it runs quite a bit faster than the brute force version. Stay tuned for more toward the end of the week.