JavaScriptで指定した範囲内の数値の最小公倍数（LCM）を求める方法

本記事では、2つの数値を要素とする配列を受け取り、その2つの数値で指定される範囲内のすべての整数の最小公倍数（LCM：Least Common Multiple）を計算して返すJavaScript関数の作成方法を解説します。

アプローチ

最小公倍数を効率的に求めるには、最大公約数（GCD）を利用するのが定番です。以下の関係式が成り立ちます。

LCM(a, b) = a × b ÷ GCD(a, b)

最大公約数は「ユークリッドの互除法」と呼ばれる古典的なアルゴリズムで簡単に求められます。この方法を使い、範囲内の各数値に対して順番に最小公倍数を累積的に計算していくことで、最終的な結果を得ることができます。

処理の手順

1. 配列の2つの要素を比較し、小さい方を範囲の開始値、大きい方を終了値として並べ替えます。
2. 開始値を初期結果として設定します。
3. 開始値から終了値までの各数値について、現在の結果とその数値の最小公倍数を順次計算します。
4. ループが完了した時点の結果が、範囲全体の最小公倍数となります。

コード例

const range = [8, 3];
const gcd = (a, b) => {
    return !b ? a : gcd(b, a % b);
}
const lcm = (a, b) => {
    return a * (b / gcd(a,b));
};
const rangeLCM = (arr = []) => {
    if(arr[0] > arr[1]) (arr = [arr[1], arr[0]]);
    for(let x = result = arr[0]; x <= arr[1]; x++) {
        result = lcm(x, result);
    }
    return result;
}
console.log(rangeLCM(range));

出力

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

840

コードの解説

gcd関数：ユークリッドの互除法を再帰的に実装したものです。第2引数bが0（falsy）になった時点でaを返すことで再帰を終了します。

lcm関数：上記のgcd関数を利用して、2つの数値の最小公倍数を計算します。

rangeLCM関数：渡された配列の要素を昇順に並べ替えた後、forループで範囲内の全整数を走査しながら最小公倍数を累積計算していきます。引数の順序が逆（この例では [8, 3] のように大きい値が先）でも正しく動作するのがポイントです。

この例の場合、範囲 [3, 8] に含まれる数値 3, 4, 5, 6, 7, 8 の最小公倍数は 840 です。実際、840はこれらすべての数値で割り切れる最小の正の整数となっています。