最大公約数を求めるプログラム

馬は最近「最大公約数を求めるプログラム」を作れることを知りました。

先輩プログラマのTさんに聞いたところ、この最大公約数をプログラムで求める課題は、プログラムを教えている学校ではよく出されて、その際に「ユークリッドの互除法」というのが使われるらしいとのことですが、

馬、そんな言葉初めて聞いたYO！😲

調べてみたら、最近高校数学で習うようになったらしいので、昭和生まれの馬は習っていませんでした。
習ってたことを欠片も覚えてないわけじゃなくて、よかった😅

ユークリッドの互除法

「ユークリッドの互除法」を簡単に説明するとこんな感じです。
例として９が最大公約数の 459（9×51）と、288（9×32）を使います。

1. 二つの数字の大きい方の数字Aを小さい数字Bで割る。
   A÷B＝割り算の答え+余りC
   ^{例）459÷288＝1余り171}
2. 次に先ほど割るのに使った小さい数字Bを、先ほどの余りCで割る。
   B÷C＝割り算の答え+余りD
   ^{例）288÷171＝1余り117}
3. 以下、割るのに使った数字を余りの数字で割っていく
   C÷D＝割り算の答え+余りE、　D÷E＝割り算の答え+余りF・・・
   ^{例）171÷117＝1余り81、　117÷81＝1余り36、　81÷36＝2余り9　（余りが0になるまで続ける）}
4. 余りが０になった数字が最大公約数
   E÷F＝割り算の答え+余りなし　→　Fが最大公約数
   ^{例）36÷9＝4余り０　→　9が最大公約数}

参考サイト）ユークリッドの互除法の証明と不定方程式　^{←馬の説明よりわかりやすい}

ユークリッドの互除法を使ったプログラム

理屈は理解できたので、PHPでプログラムを作ってみました。

とりあえず最大公約数を求める数字は、適当に385と、175に決めました。

<?php
$num1 = 385;
$num2 = 175;
$checknum = $num1%$num2;
while($checknum != 0){
    $num1 = $num2;
    $num2 = $checknum;
    $checknum = $num1%$num2;
}
echo "最大公約数：".$num2; //答えを表示
?>

これをサーバー上で実行したところ、ちゃんと

最大公約数：35

と表示されました👍

あー、すっきりしたー🐴