C# で Project Euler に挑戦: Problem 5

問題

最小の倍数

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

• Problem5 - Project Euler (公式サイト)
• Problem5 - Project Euler (和訳サイト)

ぼくの解答

static void Main(string[] args)
{
    int n = 20;

    int multiple = 1;
    int counter = 1;

    var numbers = Enumerable.Range(1, n);

    foreach (var i in numbers)
    {
        while (counter % i != 0)
        {
            counter += multiple;
        } 

        multiple = counter;
    }

    Console.WriteLine(multiple);
    Console.ReadLine();
}

解説

最小公倍数を求める問題です。単純に 1 から 20 まで順番に最小公倍数を見つけていきます。

最小公倍数を multiple として初期値を 1 とします。カウンタ用の変数(counter)も初期値を 1 にします。

1. この時点の最小公倍数(1) と 1 の最小公倍数を求める。
   • 1 / 1 = 1 ... 0 => 割り切れるので最小公倍数 を 1 に更新。
2. この時点の最小公倍数(1) と 2 の最小公倍数を求める。
   • 1 / 2 = 0 ... 1 => 割り切れないので counter に multiple を加算。
   • 2 / 2 = 1 ... 0 => 割り切れるので最小公倍数 を 2 に更新。
3. この時点の最小公倍数(2) と 3 の最小公倍数を求める。
   • 2 / 3 = 0 ... 2 => 割り切れないので counter に multiple を加算。
   • 4 / 3 = 1 ... 1 => 割り切れないので counter に multiple を加算。
   • 6 / 3 = 2 ... 0 => 割り切れるので最小公倍数 を 6 に更新。
4. この時点の最小公倍数(6) と 4 の最小公倍数を求める。
   • 6 / 4 = 1 ... 2 => 割り切れないので counter に multiple を加算。
   • 12 / 4 = 3 ... 0 => 割り切れるので最小公倍数 を 12 に更新。
5. この時点の最小公倍数(12) と 5 の最小公倍数を求める。
   • 12 / 5 = 2 ... 2 => 割り切れないので counter に multiple を加算。
   • 24 / 5 = 4 ... 4 => 割り切れないので counter に multiple を加算。
   • 36 / 5 = 7 ... 1 => 割り切れないので counter に multiple を加算。
   • 48 / 5 = 9 ... 3 => 割り切れないので counter に multiple を加算。
   • 60 / 5 = 12 ... 0 => 割り切れるので最小公倍数 を 60 に更新。
6. この時点の最小公倍数(60) と 6 の最小公倍数を求める。
   • 60 / 6 = 10 ... 0 => 割り切れるので最小公倍数 を 60 に更新。
7. ... という風に続く。

他のプローチ

調べたら他にも良さそうなやり方がありました。最大公約数を元に解くのとか、数学っぽくていいですね。ぼくの頭では思いつきませんでした...

• 最大公約数と最小公倍数