CodeProject
Ready or not, here comes problem five!
2520 is the smallest number that can be divided by each of the numbers
from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of
the numbers from 1 to 20?
This one really doesn't require that much explanation. I suppose we could easily brute force this one also, but that just isn't my style. So I'll just go ahead and show the final return
statement that gives us the answer:
return Enumerable.Range(1, 20).Aggregate(this.LeastCommonDivisor);
....Alright....that's it. Let's go home.
No?
Okay fine. Let me explain a bit. We are using the 'Aggregate
' Extension here on our range of 1-20. The 'Aggregate
' method will take our recursive method 'LeastCommonDivisor
'.
Here is that function:
private int LeastCommonDivisor(int i, int j)
{
return (i == 0) || (j == 0) ? 0 : (i / this.GreatestCommonDivisor(i, j)) * j;
}
That function also makes reference to this function to recursively find the greatest common divisor:
private int GreatestCommonDivisor(int i, int j)
{
return (j == 0) ? i : this.GreatestCommonDivisor(j, i % j);
}
Now our 'Aggregate
' method will calculate the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.
This problem was not that enjoyable to me, but oh well. I found some great references by Basildon Coder and Functional Fun. From these guys, I was able to figure something out. Anyways, here it is. Do with it what you will.