Project Euler #5 - Lowest common multiple of 1 through 20

Question

This is my code. All comments welcome. Last time run it only took 335 milliseconds:

static bool CheckMultiples(int val)
{
    for (int i = 1; i <= 20; i++)
    {
        if (val % i != 0)
            return false;
    }

    return true;
}

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int Num = 20;
    while (!CheckMultiples(Num))
    {
        Num += 20;
    }

    s.Stop();

    Console.WriteLine("The smallest number divisible by all numbers 1-20 is {0}.", Num);
    Console.WriteLine("The time took is {0} milliseconds.", s.ElapsedMilliseconds);
}

Answer 1

There is a far more efficient approach to finding the least common multiple (\$\operatorname{lcm}\$) of a set of integers which, unlike your and rolfl's code, involves no trial-and-error. Recall that for any pair \$(a, b)\$ of natural numbers, we have $$\operatorname{lcm}(a, b) = \frac{ab}{\operatorname{gcd}(a, b)}.$$ This reduces the implementation of \$\operatorname{lcm}\$ to the implementation of \$\operatorname{gcd}\$, which is easily done using the simple and efficient Euclidean algorithm. Then, calculating the least common multiple of \$\{1, 2, ..., 20\}\$ is as simple as \$\operatorname{reduce}(\operatorname{lcm}, \{1, 2, ..., 20\})\$.

You can find a simple Python 3 implementation of this idea in ideone here. Even in a slow interpreted language like Python, this is several orders of magnitude faster than your or rolfl's code, running in about .04 milliseconds.

Answer 2

There are a few optimizations you can do to reduce the amount of work you do. For the most part, it comes down to understanding the math behind the concept.

First off, if you have found the minimum common multiple for a small set of numbers to be X, then want to include another value in the set.... then the resulting minimum common multiple will be a multiple of X. Say, for example, you have the values 2, and 3, and the minimum multiple for those is 6. Now you want to find the minimum common multiple for 2, 3, and 4, then the resulting multiple 12 is also a multiple of 6. If we want to add the number 5 to the set, becoming 2, 3, 4, 5, then we know that the minimum common multiple will be a multiple of 12 too (and it is, it's 60). Taking it another step, if we add 6 to the set, well, 60 is already a multiple of 6, so there's nothing to do....

OK, so that's optimization 1.... instead of adding 20 each time, we can add the previously calculated minimum .... and now we are adding 60 already....which is 3 times faster than adding 20... throw 7 in to the mix, and the multiple is.... 420 ... which is now 21-times faster than adding 20's.

The next optimization is to do things backwards.... instead of starting from 1, start from 20....

The smallest common multiple for 20, and 19, is 380. and in to that, add 18, and the multiple is.... 3420 .... now our increments are much larger than 20....

In addition to the larger increments each time, by starting at the end you also already include lower multiples. For example, 20 is a multiple of 10, 5, 4, and 2 so when we get to those lower multiples there will be nothing to do.

Putting these two optimizations together, we end with the following code:

public static int MinMultiples(int from)
{
    int multiple = from;
    for (int m = from - 1; m > 1; m--)
    {
        int extend = multiple;
        Console.WriteLine("Multiple {0} extending by {1}", m, extend);
        while ((multiple % m) != 0)
        {
            multiple += extend;
        }
    }
    return multiple;
}

I have put this in an Ideone here, and Ideone claims it runs in... 0.03 seconds.

Answer 3

Like many Project Euler problems, your answers can be much improved by taking a step back and thinking about the problem at hand.

The question is asking for the number that is divisible by every integer less than or equal to 20.

The way to think about this is to find the common factors when reducing each integer to its prime factors.

Start by finding all primes less than 20. Then you need to find the highest power of each prime that is less than 20 and find the product of all these.

The answer then comes out as:

2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 == 232792560

In generality, you would solve this by sieving the primes and finding the product of the highest power of each prime less than or equal to the number you are calculating for.

Answer 4

If you consider finding all primes under 20 to be so trivial, that it doesn't require computation, then below is an example JavaScript code (you can open your browser console and run it there), which was the only reason I choose this language for demonstration:

function euler5() {
    function mul(a, b) { return a * b; }
    var multipliers = [2, 3, 5, 7, 11, 13, 17, 19],
        total = multipliers.reduce(mul), original, j;
    for (var i = 0; i <= 20; i++) {
        original = total;
        j = 0;
        while (original % i)
            original = total * multipliers[j++];
        total = original;
     }
    return total;
}

Trying to be more languaga-agnostic, here's the same idea in Prolog:

multiple([], X, X).
multiple([X | Xs], Acc, Result) :-
    Next is X * Acc,
    multiple(Xs, Next, Result).

multiple(Factors, Result) :-
    multiple(Factors, 1, Result).

product_of(_, Test, _, Of, Test) :-
    Mod is Test mod Of,
    Mod is 0, !.
product_of(Product, Test, [X | Xs], Of, Result) :-
    Mod is Test mod Of,
    Mod \= 0,
    Next is X * Product,
    product_of(Product, Next, Xs, Of, Result).

euler5(21, _, Product, Product).
euler5(N, Factors, Product, Result) :-
    product_of(Product, Product, Factors, N, Next),
    N1 is N + 1,
    euler5(N1, Factors, Next, Result).
euler5 :-
    Factors = [2, 3, 5, 7, 11, 13, 17, 19],
    multiple(Factors, Mul),
    euler5(4, Factors, Mul, Result),
    print(Result), nl.

The basic idea is that you first multiply all the primes and then, if the total isn't multiple of the next number, you look into your primes for the one to multiply with. Doing this in increasing order ensures that there will be no gaps which would require that you multiply by more than one prime factor at a time.

Needless to say that this runs in a tiny fraction of a second.