今更聞けないユークリッドの互除法(最大公約数)

高校数学で習うユークリッドの互除法をC#で実装します。
https://github.com/ma3100/AlgorithmPrimer/blob/master/FirstAlgorithmForCSharp/First/Euclidean.cs

ユークリッドの互除法とは？

数Aで習う、2つの整数a,bの最大公約数を求める公式です。
細かい公式は家庭教師のトライさんあたりがしてくれているので割愛します。

高校数学では余剰を求める方法で解くのが一般的ですが、今回は減算する方法も紹介します。

余剰で求める方法

1. aをbで割って、余りをcに入れる。
2. aにbを、bにcを代入する。
3. cが0でなければ1に戻る。
4. aに入っている値が最大公約数である。

文字でイメージ出来ない場合、以下画像でイメージを膨らませてください。

division.cs

        public int divisionPattern(int a,int b)
        {
            var divisionValue = -1;

            while(divisionValue != 0)
            {
                divisionValue = a % b;
                a = b;
                b = divisionValue;
            }

            Console.WriteLine($"Answer:{a}");
            return a;
        }

減算で求める方法

1. aとbの内、大きい方 - 小さい方の答えを大きい方の変数に代入する。
2. aとbが等しくなければ1に戻る。
3. aに入っている値が求める最大公約数である。

文字でイメージ出来ない場合、以下画像でイメージを膨らませてください。

minus.cs

        public int minusPattern(int a,int b)
        {
            while(a != b)
            {
                if(a > b)
                {
                    a -= b;
                }
                else
                {
                    b -= a;
                }
            }

            Console.WriteLine($"Answer:{a}");
            return a;
        }

所感

コンピューター的には、当然余剰で求める方が効率良いです。
数学アレルギーを持つ人に対しては、減算の方が簡単だし驚きも生まれるから場合によっては紹介しても良いのかな程度です。