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 number that is evenly divisible by all of the numbers from 1 to 20?
This is a problem that can be brut forced. But a more elegant solution involves finding the least common multiple of all the numbers combined. The least common multiple of two numbers can be calculated using their greatest common divisor (GCD), or the largest number that divides evenly into both numbers. F# happens to include its math library a method for calculating the GCD called BigInt.hcf (hcf = highest common factor another name for GCD). This makes problem 5 really easy in F# (easier than C#).
open Microsoft.FSharp.Math
let lcm i j =
if i = 0I or j = 0I then 0I
else (i / (BigInt.hcf i j)) * j
let lowest = [1I..20I] |> List.fold1_left lcm
C#
class Program
{
static public int GCD(int i, int j)
{
if (j == 0) return i;
else return GCD(j, i % j);
}
static public int LCM(int i, int j)
{
if (i == 0 || j == 0) return 0;
return (i / GCD(i, j)) * j;
}
static void Main(string[] args)
{
var t = Enumerable.Range(1, 20).Aggregate(LCM);
Console.WriteLine(t);
Console.ReadLine();
}
}
del.icio.us Tags:
C#,
F#,
Project Euler