【JavaScript】配列の全要素を割り切れるn桁の最小の数を求める方法

本記事では、第一引数に整数 n、第二引数に数値の配列を受け取り、「配列のすべての要素で割り切れる n 桁の最小の数」を返す JavaScript 関数の実装方法を解説します。

もし該当する n 桁の数が存在しない場合は、条件を満たす最小の数をそのまま返します。

問題の例

たとえば、次のような配列が与えられたとします。

const arr = [12, 4, 5, 10, 9];

この場合、n = 2 のときも n = 3 のときも、期待される出力は次のとおりです。

180

これは、12・4・5・10・9 のすべてを割り切れる最小の数（最小公倍数）が 180 であり、180 は 2 桁にも 3 桁にも該当するためです。

シンプルな実装例

まずは、最も理解しやすい「総当たり（ブルートフォース）」方式のコードを見てみましょう。

const arr = [12, 4, 5, 10, 9];
const num1 = 2;
const num2 = 3;

// num が配列の全要素で割り切れるかどうかを判定
const allDivides = (arr, num) => arr.every(el => num % el === 0);

// n 桁の最小値から順に探索
const smallestMultiple = (arr, num) => {
    let smallestN = Math.pow(10, num - 1);
    while (!allDivides(arr, smallestN)) {
        smallestN++;
    }
    return smallestN;
};

console.log(smallestMultiple(arr, num1));
console.log(smallestMultiple(arr, num2));

コードの解説

allDivides 関数

Array.prototype.every() メソッドを利用し、引数 num が配列内のすべての要素で割り切れるかどうかを真偽値で返します。

smallestMultiple 関数

n 桁の数のうち最も小さい値 10^(n-1)（例：n = 2 なら 10）を初期値とし、条件を満たす数が見つかるまで 1 ずつ増やしながら探索を行います。

実行結果

180
180

より効率的な方法：GCD と LCM を活用する

総当たり方式はシンプルですが、答えが大きくなるとループの反復回数が膨大になり、パフォーマンスが大きく低下します。

そこで役立つのが数学的なアプローチです。「配列の全要素で割り切れる最小の数」は、配列全体の最小公倍数（LCM）と等しいため、ユークリッドの互除法で最大公約数（GCD）を求めれば、ループ処理なしで瞬時に答えを導き出せます。

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

// 最小公倍数
const lcm = (a, b) => (a * b) / gcd(a, b);

// 配列全体の LCM を求め、n 桁以上の最小の倍数を返す
const smallestMultipleFast = (arr, num) => {
    const base = arr.reduce((acc, el) => lcm(acc, el));
    return Math.ceil(Math.pow(10, num - 1) / base) * base;
};

console.log(smallestMultipleFast([12, 4, 5, 10, 9], 2)); // 180
console.log(smallestMultipleFast([12, 4, 5, 10, 9], 3)); // 180

この方式であれば、配列の要素数や数値の大きさにかかわらず、ほぼ一定の時間で結果を取得できます。実務では、こちらのアプローチを採用することをおすすめします。