PHPで最大公約数（ユークリッドの互除法）

ユークリッドの互除法を使って2つの数の最大公約数を求める実装例です。コピペで動くコードと実行結果、処理の流れを確認できます。 下のコードはブラウザ内でそのまま実行できます。「実行エディタで開く」を押すと、progoのオンラインPHP実行環境にコードが読み込まれ、その場で動作を確認できます。

サンプルコード

function gcd($a, $b) {
    while ($b != 0) {
        [$a, $b] = [$b, $a % $b];
    }
    return $a;
}
echo gcd(48, 18) . "\n";
echo gcd(1071, 462) . "\n";

ポイント解説

• 余りが0になるまで剰余の計算を繰り返します。
• 分割代入で$aと$bを更新します。
• 少ない計算量で最大公約数を求められます。