最大公約数・最小公倍数を求める(ユークリッドの互除法)

このレッスンでは、ユークリッドの互除法を使って最大公約数と最小公倍数を求める方法を学び、再帰関数の基本を体験することを目標にします。「PHP 最大公約数求め方」で調べている方向けです。

ユークリッドの互除法は、2つの数の最大公約数(GCD)を効率よく求める古代からのアルゴリズムです。「大きい方を小さい方で割った余りで、また同じ計算を繰り返す」を余りが0になるまで続けます。

サンプルコードでは、gcdFunc($a, $b)関数が$b === 0になるまでgcdFunc($b, $a % $b)という形で自分自身を呼び出し続けています。最小公倍数(LCM)は、最大公約数を使った計算式($a * $b) / gcdFunc($a, $b)で求められる、という2つのアルゴリズムのつながりも確認してみましょう。

初心者がよくつまずくのが、なぜこの計算式で最小公倍数が求まるのかという理屈です。2つの数の積を最大公約数で割ると最小公倍数になる、という数学的な関係を知っておくと、単なる暗記ではなく理解を伴った実装ができます。

自作するより組み込みの考え方を使う方が安全で、アルゴリズムの理解にもつながる練習題材です。再帰関数の練習題材としても非常によく使われる、数学とプログラミングの両方の基礎が詰まった有名なアルゴリズムです。

📖 お手本コード

<?php
function gcdFunc($a, $b) {
    return $b === 0 ? $a : gcdFunc($b, $a % $b);
}

function lcmFunc($a, $b) {
    return ($a * $b) / gcdFunc($a, $b);
}

echo "最大公約数: " . gcdFunc(12, 18) . "\n";
echo "最小公倍数: " . lcmFunc(4, 6);

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではPHPを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
分数を約分するような、ミニ計算ツールが作れるようになります。