ユークリッドの互除法を使ってJavaScriptで最大公約数（GCD）を求める方法

数学におけるユークリッドの互除法（Euclid's algorithm）とは、2つの数の最大公約数（GCD）、すなわち両方の数を余りなく割り切れる最大の数を求めるための古典的なアルゴリズムです。

このアルゴリズムは、「2つの数の最大公約数は、大きい方の数を『大きい数から小さい数を引いた差』に置き換えても変化しない」という原理に基づいています。

例えば、252 と 105 の最大公約数は 21 です（252 = 21 × 12、105 = 21 × 5）。同様に、105 と 147（= 252 − 105）の最大公約数もやはり 21 になります。

この置き換えを行うたびにペアの中の大きい方の数は必ず小さくなるため、操作を繰り返すと2つの数は次第に近づき、最終的には等しくなります。その時点での値こそが、元の2つの数の最大公約数です。

さらに、手順を逆向きにたどれば、最大公約数を「元の2つの数に整数を掛けて足し合わせた形」で表すこともできます。例えば、21 = 5 × 105 + (−2) × 252 となります。

本記事では、2つの数を受け取り、ユークリッドの互除法を用いてそれらの最大公約数（GCD）を計算するJavaScript関数を実装していきます。

コード例

以下が実際のコードです。

const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
    let a = Math.abs(num1);
    let b = Math.abs(num2);
    while (a && b && a !== b) {
        if(a > b){
            [a, b] = [a - b, b];
        }else{
            [a, b] = [a, b - a];
        };
    };
    return a || b;
};
console.log(findGCD(num1, num2));

出力結果

コンソールには以下のように表示されます。

21

コードの解説

まず Math.abs() を使って引数を絶対値に変換することで、負の数が渡された場合にも正しく動作するようにしています。

while ループの中では、大きい方の数から小さい方の数を引き続けることで、2つの値が等しくなるまで処理を反復します。分割代入 [a, b] = [a - b, b] を使うことで、値の入れ替えを簡潔に記述できるのがポイントです。

ループが終了した時点で、a || b によって残っている値（0でない方）が最大公約数として返されます。片方が0になった場合も、もう片方の値がそのまま答えになるため、この書き方で両方のケースをカバーできます。

なお、この減算による実装は原理が理解しやすい一方、差が大きい場合はループ回数が増えます。実務では剰余演算子 % を使った実装の方が高速に動作するため、用途に応じて使い分けるとよいでしょう。