JavaScriptで数値配列の範囲内すべての最小公倍数を求める方法

問題の概要

2つの数値からなる配列で範囲が指定されているとします。ここで求めたいのは、指定された2つの数値の両方、さらにその範囲内に含まれるすべての連続する整数でも割り切れるような最小公倍数（LCM）を計算する関数です。

なお、範囲を表す配列の2つの数値は、必ずしも昇順に並んでいるとは限りません。そのため、処理の前にソートしておく必要があります。

例えば [1, 3] が与えられた場合、1と3の最小公倍数であり、かつ1から3までのすべての整数（1・2・3）でも割り切れる数を求めます。この場合の答えは 6 です。

コード例

実際のコードは以下のようになります。

const range = [1, 12];

const smallestCommon = (array = []) => {
    const arr = array.slice().sort((a, b) => a - b);
    let result = [];

    // 範囲内のすべての整数を配列に格納
    for (let i = arr[0]; i <= arr[1]; i++) {
        result.push(i);
    }

    // 大きい方の数値の倍数を順に確認し、
    // すべての数値で割り切れる最初の倍数を返す
    let i = 1;
    let res;
    while (result.every(item => res % item == 0) == false) {
        i++;
        res = arr[1] * i;
    }
    return res;
};

console.log(smallestCommon(range));

実行結果

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

27720

コードの解説

このアルゴリズムの流れは以下の通りです。

1. slice() で元の配列を破壊しないようにコピーし、sort() で昇順に並べ替えます。
2. 範囲の最小値から最大値までの整数をすべて配列に格納します。
3. 最大値の倍数（最大値 × i）を順番に生成し、範囲内のすべての数値で割り切れるかどうかを every() で判定します。
4. 最初に条件を満たした倍数が、求める最小公倍数となります。

より効率的な実装：ユークリッドの互除法を使う

上記の方法はシンプルですが、範囲が大きくなると試行回数が増えて非効率になります。最小公倍数は「最大公約数（GCD）」を使って求めるのが定石です。

2つの数 a, b の最小公倍数は a × b ÷ gcd(a, b) で計算できるため、これを範囲内の数値に順番に適用していきます。

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

const smallestCommon = (array = []) => {
    const arr = array.slice().sort((a, b) => a - b);
    let result = arr[0];

    for (let i = arr[0] + 1; i <= arr[1]; i++) {
        result = lcm(result, i);
    }
    return result;
};

console.log(smallestCommon([1, 12])); // 27720

こちらの方法では、範囲内の数値を一度だけ走査すればよいため、大きな範囲に対しても高速に動作します。