JavaScriptで1からnまでのすべての数で割り切れる最小の数を求める方法

JavaScriptで数値 n を引数として受け取り、1 から n までのすべての整数で余りなく割り切れる最小の数を見つけて返す関数を作成します。この問題は、数学でいう「最小公倍数(LCM)」を 1〜n の範囲で求めることと同じです。

アルゴリズムの考え方

1 から n までの最小公倍数を効率的に求めるには、n 以下の各素数 p に対して「p の累乗のうち n 以下になる最大の値」を求め、それらをすべて掛け合わせます。

例として n = 20 の場合を見てみましょう。20 以下の素数は 2, 3, 5, 7, 11, 13, 17, 19 で、それぞれ使うべき最大の累乗は次のとおりです。

• 2 → 16(2の4乗)
• 3 → 9(3の2乗)
• 5 → 5
• 7 → 7
• 11 → 11
• 13 → 13
• 17 → 17
• 19 → 19

これらを掛け合わせると 232792560 となり、これこそが 1〜20 のすべての数で割り切れる最小の数です。

サンプルコード

const smallestDivisible = (num) => {
   let i, n = 1;
   // 素数 n の累乗のうち、num 以下で最大の値を返す
   const largestPower = (n, num) => {
      let p, e = 2, largest = n;
      while ((p = Math.pow(n, e)) <= num) {
         largest = p;
         e += 1;
      }
      return largest;
   }
   // 素数判定(奇数のみを対象とする前提)
   const isPrime = n => {
      let i, num = Math.ceil(Math.sqrt(n));
      for (i = 3; i <= num; i += 2) {
         if (n % i === 0) {
            return false;
         }
      }
      return true;
   }
   // 3 以上の奇数の素数について最大累乗を積み上げる
   for (i = 3; i <= num; i += 2) {
      if (isPrime(i)) {
         n *= largestPower(i, num);
      }
   }
   // 最後に 2 の最大累乗を掛けて完成
   return n * largestPower(2, num);
}
console.log(smallestDivisible(20));

実行結果

232792560

コードのポイント

• largestPower 関数: 素数 n を底とする累乗のうち、num 以下で最大のものを返します。たとえば (2, 20) を渡すと 16 を返します。
• isPrime 関数: 与えられた数が素数かどうかを判定します。平方根までの奇数だけで割り切れるかを確認するため、効率的な実装になっています。この関数は奇数に対してのみ呼び出されるため、偶数の扱いは考慮不要です。
• メインループ: 3 以上の奇数だけを順に調べ、素数であればその最大累乗を積に掛けます。最後に 2 の最大累乗を掛ければ、1〜num の最小公倍数が完成します。

この手法を使えば、1 から順番に全数を総当たりでチェックする方法よりもはるかに高速に正解を導き出せます。