最大公約数の計算

アルゴリズムのお勉強してるとよく出てくるやつ。
ユークリッドの互除法をC#で実装してみました。

using System;

namespace gcd
{
    class Program
    {
        static void Main()
        {
            // 試しに動かしてみる
            Console.WriteLine(GetGCD(24, 9));
        }

        /// <summary>
        /// 最大公約数を計算する
        /// </summary>
        /// <remarks>
        /// メソッド名のGCDはGreatest Common Divisorの略
        /// </remarks>
        /// <param name="a">割られる数</param>
        /// <param name="b">割る数</param>
        /// <returns>最大公約数</returns>
        static int GetGCD(int a, int b)
        {
            while (true)
            {
                int r = a % b;

                // 割り切れたら(あまりが0なら)終わり
                if (r == 0)
                {
                    return b;
                }
                else
                {
                    // 割る数に使っていた数を割られる数に設定
                    a = b;

                    // 余りを割る数に設定
                    b = r;
                }
            }
        }

    }

}

GetGCDのelse文あたりの理屈は大体こんな感じ。

最大公約数をgとすると a=p×g, b=q×g (p,qは適当な整数)
aをbで割ったときの商をs,余りをtとすると a=s×b+t。(sも適当な整数)

左辺も右辺もgの倍数。
右辺のs×bもgの倍数。
なのでtもgの倍数になるはず。

つまり、割る数と割られる数の最大公約数は
割られる数と余りの最大公約数に等しい。

おわり。