Project Euler : Problem 5 『Smallest multiple』

Laboratoire de Chimie Moléculaire (LCM) / ecolepolytechniqueups

問題

　1から20全てで割り切れる最小の数を求めよ。

全部掛けたらええやん

　仮に1から5まで全部で割り切れる最小の数を作ろうとする場合、
手っ取り早く思いつくのは全部を掛けること。
\(1 \times 2 \times 3 \times 4 \times 5 = 120\)
というわけで、120が「1から5まで全部で割り切れる数」ということになります。

　でもこれはまだ条件を満たしてない。
条件は「1から5まで全部で割り切れる最小の数」。
最小の数は、実は60。
\(60 = 2 \times 30 = 3 \times 20 = 4 \times 15 = 5 \times 12\)
と、こんな感じで、1から5全てで割り切れることがわかります。

最小公倍数(lcm , Least Common Multiple)

　全部掛けるのはどうやら違うっぽいので、別の方法が必要になりました。
しばらく悩んでましたが、要は最小公倍数を求めればいいんじゃないかと。
2と3の最小公倍数(lcm)を考えて、その答えと4のlcmを考えて、その答えと……。

　とりあえず手計算でやってみると、
\( lcm(lcm(lcm(2,3),4),5) = lcm(lcm(6,4),5) = lcm(12,5) = 60 \)
というわけで、順に最小公倍数を調べていけばいい、ということがわかりました。
じゃぁ、最小公倍数ってどうやって求めるの？勘？

あれ何て言ったっけ、あの、神っぽい感じの綴りのあれ

　gcd(greatest common divisor、最大公約数)でした。
godっぽいと常々思ってます。
それはさておき、2つの整数a,bの最小公倍数(lcm)と最大公約数(gcd)の関係は、
\(a \times b = lcm \times gcd\)
こうなっています。
gcdはユークリッド互除法という有名な方法でパパーと算出できるので、lcmを求めるには
\( lcm = \frac{a \times b}{gcd}\)
こんな感じで計算すればいいでしょう。

　24と9で試しの計算をしてみます。
\( 24 \times 9 = lcm \times 3 \)
\( \frac{216}{3} = lcm \)
\( lcm = 72 \)
というわけで24と9の最小公倍数は72、となりました。

　与えられた問題に対しては、
これを1から20まで順番にやっていけば答えが出る、ということですね。

コード

using System;
using System.Diagnostics;

namespace Problem5
{
    class Program
    {
        static void Main(string[] args)
        {
            Int64 e = 2;
            for(int i = 3; i <= 20; i++)
            {
                Int64 p = EA(e, i);
                e = (e * i) / p;
            }
            Debug.WriteLine(e);

        }

        //ユークリッド互除法
        static Int64 EA(Int64 a, Int64 b)
        {
            while((a != 0) & (b != 0))
            {
                if (a >= b) a = a % b;
                else b = b % a;
            }

            return (a != 0) ? a : b;
        }
    }
}