Return to Revisions

You can have both performance and readability using the newly-introduced (.NET 4.0) method BigInteger.GreatestCommonDivisor (a reference to System.Numerics is required).

With the BigInteger stuct, you gain an additional advantage: your code will work for arbitrarily large numbers (assuming sufficient memory).

var result = ClosedInterval(1, 20).LeastCommonMultiple();

What we are looking for is the least common multiple of all natural numbers in the interval [1, 20], so we'll need a method to generate them (closed means including both bounds and the numbers between):

static IEnumerable<BigInteger> ClosedInterval(BigInteger first, BigInteger last)
{
    for (var i = first; i <= last; i++)
    {
        yield return i;
    }
}

From Wikipedia, we know how to calculate the least common multiple of two numbers:

static BigInteger LeastCommonMultiple(BigInteger a, BigInteger b)
{
    return (a * b) / BigInteger.GreatestCommonDivisor(a, b);
}

For an arbitrary number of least common multiples, we simply aggregate them using LINQ and package the logic in an extension method:

static BigInteger LeastCommonMultiple(this IEnumerable<BigInteger> divisors)
{
    return divisors.Aggregate(LeastCommonMultiple);
}

The implementation calculates the correct result (232792560) in less than one tenth of a millisecond on my machine.

In less than half a second, you can find out the answer for an input of [0, 20000]; The solution is over eight thousand digits long and therefore somewhat outside the scope of this answer.