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

問題

数値 n を引数として受け取る JavaScript 関数を作成する必要があります。この関数は、1 から n までのすべての整数で割り切れる最小の正の整数を求めて返します。

実は、この問題は数学における「最小公倍数(LCM)」を求める問題と同じです。1 から n までのすべての数値の最小公倍数こそが、求めるべき答えとなります。

例

n = 10 の場合を考えてみましょう。2520 という数値は、1・2・3・…・10 のすべての数値で余りなく割り切ることができる、最も小さい数値です。

以下のコードを見てみましょう −

const num = 11;
const smallestDivisible = (num = 1) => {
    let res = num * (num - 1) || 1;
    for (let i = num - 1; i >= 1; i--) {
        if (res % i) {
            for (let j = num - 1; j >= 1; j--) {
                if (!(i % j) && !(res % j)) {
                    res = i * res / j;
                    break;
                }
            }
        }
    }
    return res;
}
console.log(smallestDivisible(num));

出力

27720

コードの解説

このアルゴリズムの流れは次のとおりです。

• 初期値として res = num × (num - 1) を設定します(num が 1 の場合は 1)。連続する 2 つの数は互いに素であることが多いため、ここから始めると効率的です。

• 外側のループで i を num - 1 から 1 まで降順に調べます。

• もし res が i で割り切れない場合(res % i が真)、内側のループで j を降順に調べ、「i と res の両方を割り切れる最大の共通因数 j」を見つけます。

• その j が見つかったら、res = i × res ÷ j として更新します。こうすることで、既存の約数関係を壊さずに、res を i でも割り切れる数へ拡張できます。

• すべてのループが終わった時点での res が、1 から n までのすべての数値で割り切れる最小の数値(= 最小公倍数)です。

num = 11 の場合の出力は 27720 となり、これは実際に 1〜11 のすべての整数で割り切れる最小の数値です。

別解：GCD(最大公約数)を使うシンプルな方法

より直感的なアプローチとして、「隣接する 2 数の LCM を順番に計算していく」方法もあります。ユークリッドの互除法で最大公約数(GCD)を求めれば、LCM は 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 smallestDivisible = (num = 1) => {
    let res = 1;
    for (let i = 2; i <= num; i++) {
        res = lcm(res, i);
    }
    return res;
};

console.log(smallestDivisible(11)); // 27720

こちらの方法はコードが短く理解しやすいため、実務や面接では特におすすめです。ただし、大きな n を扱う場合は Number 型の安全な整数範囲(Number.MAX_SAFE_INTEGER)を超える可能性がある点には注意してください。