JavaScriptで最小公倍数（LCM）を求める方法｜1〜nの全自然数で割り切れる最小の数

本記事では、数値を1つ引数として受け取り、1からnまでのすべての自然数で割り切れる最小の数を見つけるJavaScript関数の作成方法を解説します。この「最小の数」こそが、数学でいうところの最小公倍数（LCM）です。

問題の例

例えば、n = 4 の場合、出力は 12 になります。
これは、12が「1・2・3・4」のすべての数で余りなく割り切れる、最も小さい数だからです。

サンプルコード（総当たり方式）

まずは、候補となる数を1つずつ検証していくシンプルな実装から見ていきましょう。

const smallestMultiple = num => {
    let res = 0;
    let i = 1;
    let found = false;
    while (found === false) {
        res += num;
        while (res % i === 0 && i <= num) {
            if (i === num) {
                found = true;
            }
            i++;
        }
        i = 1;
    }
    return res;
};
console.log(smallestMultiple(2));
console.log(smallestMultiple(4));
console.log(smallestMultiple(12));
console.log(smallestMultiple(15));

実行結果

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

2
12
27720
360360

コードの仕組み

この関数は単純なアプローチながら、いくつかの工夫が施されています。

• numずつ加算： 変数resに引数numを繰り返し足していくことで、必ずnumの倍数だけを候補としてチェックできます。1ずつ増やす場合に比べ、無駄な試行を大幅に削減できます。
• 割り切れるかの検証： 内側のwhileループで、現在のresが1からnumまでの各整数で余りなく割り切れるかを順番に確認します。
• 終了条件： iがnumに達し、かつresがそれで割り切れた時点でフラグfoundをtrueにし、その値を結果として返します。

より効率的な方法：GCD（最大公約数）を活用する

上記の方法は分かりやすい反面、nが大きくなると処理時間が急激に伸びてしまいます。そこでおすすめしたいのが、次の公式を使ったアプローチです。

最小公倍数(a, b) ＝ a × b ÷ 最大公約数(a, b)

ユークリッドの互除法で最大公約数（GCD）を求め、1からnまで順番に最小公倍数を畳み込んでいくことで、非常に高速に答えを得られます。

// ユークリッドの互除法による最大公約数
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

// 1からnまでの最小公倍数を求める
const lcmOfRange = n => {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result = (result * i) / gcd(result, i);
    }
    return result;
};
console.log(lcmOfRange(4));   // 12
console.log(lcmOfRange(10));  // 2520
console.log(lcmOfRange(15));  // 360360

この手法なら、nが数百規模になっても一瞬で計算できます。「1から20までの整数すべてで割り切れる最小の数」を問う有名なプログラミング課題（Project Euler Problem 5）も、この方法なら簡単に解くことができます。実務や競技プログラミングでは、こちらのGCDベースの実装を選ぶのが賢明でしょう。