[JavaScript] 最大公約数を求める

はじめに

この記事では、以下のテクニックを扱います。

• 数値 a, b の最大公約数を求める

求めてみる

まずはシンプルに

とくに考えず実装した場合、以下のようになるかと思います。
ふたつの値のうち小さいほうをaとし、2~a までの範囲の数のうち、a と b 両方を割り切れる最大の数を求めていきます。

const gcd = (a, b) => {
    // a < b とする
    let maxDivisor = 1;  // 最大公約数
    for(let div=2; div<=a; div++) {
        if(a % div === 0 && b % div === 0) {
            maxDivisor = div;
        }
    }
    
    return maxDivisor;
}

gcd は greatest common divisor = 最大公約数　のことです。
時間計算量は O(a) (a<b) 、空間計算量は O(1) となります。

互除法を使う

さて、ここからが本題です。

数学の世界では、最大公約数の計算にはユークリッドの互除法が使われます。
このアルゴリズムは、以下のように説明されます。

a を b で割ったあまりを r と仮定する。
a と b の最大公約数と、b と r の最大公約数は等しい。

これを利用して、以下のような手順で計算を行います。

1. a, b のうち一方が 0 ではないかチェックする
   2. そうだった場合、0 ではないほうが最大公約数となる
2. 大きいほうから小さいほうを割る
3. 大きいほうを余りで置き換える
4. 1へ戻る

たとえば、32 と 48 の最大公約数を求めてみます。
以下のように、割り算からあまりを取り出し、小さいほうを余りで割り続けます。

さて、長らく説明しましたが、これをコードで表現すると以下のようになります。

const gcd = (a, b) => {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
};

小さいほう = b に 0 が現れるまで再帰を繰り返す、再帰関数として実装しました。
条件式がシンプルなので、三項演算子でまとめることもできます。

const gcd = (a, b) => b == 0 ? a : gcd(b, a % b);

かなりさっぱりしましたね。個人的にはこっちがお気に入りです。

計算量については数学に明るくないので確証はありませんが、多くの記事では O(log(min(a,b))) とされています。要するに小さいほうの数の対数をとったものですね。

参考

https://algo-method.com/descriptions/124
https://leetcode.com/problems/find-greatest-common-divisor-of-array/