JavaScriptで数値の約数の個数を求める方法

問題

JavaScriptで、引数として受け取った数値の約数（divisor）の個数を返す関数を作成する必要があります。

入力

const num = 30;

出力

const output = 8;

30の約数は以下の8個だからです。

1, 2, 3, 5, 6, 10, 15, 30

アプローチ：素因数分解を使う

このコードでは、1から順に割り切れる数を探して数えるのではなく、素因数分解の性質を利用しています。

任意の正の整数 n を素因数分解して n = p^a × q^b × r^c ... と表せるとき、約数の総数は次の式で求められます。

(a + 1) × (b + 1) × (c + 1) × ...

例えば 30 = 2 × 3 × 5 なので、(1+1) × (1+1) × (1+1) = 8 個となります。この方法なら、約数をすべて列挙するよりも効率的に個数だけを計算できます。

アルゴリズムの流れ

1. 2から始まる除数（div）で、num が割り切れなくなるまで割り続けます。
2. 割り切れた場合は、その素因数と出現回数を配列 divArr に記録します。
3. 割り切れない場合は、除数を1つ増やして再試行します。
4. 最後に、各素因数の出現回数 + 1 をすべて掛け合わせた値が答えになります。

コード例

以下が実際のコードです。

const num = 30;
const countDivisors = (num = 1) => {
    if (num === 1) return num
    let divArr = [[2, 0]]
    let div = divArr[0][0]
    while (num > 1) {
        if (num % div === 0) {
            for (let i = 0; divArr.length; i++) {
                if (divArr[i][0] === div) {
                    divArr[i][1] += 1
                    break
                } else {
                    if (i === divArr.length - 1) {
                        divArr.push([div, 1])
                        break
                    }
               }
           }
            num /= div
        } else {
            div += 1
        }
    }
    for (let i = 0; i < divArr.length; i++) {
        num *= divArr[i][1] + 1
    }
    return num
}
console.log(countDivisors(num));

出力結果

8

解説

この関数は以下のように動作します。

• num === 1 の場合は約数が「1」のみなので、そのまま1を返します。
• divArr は [素因数, 指数] のペアを格納する配列です。30の場合、最終的に [[2, 1], [3, 1], [5, 1]] になります。
• whileループ内で、num を素因数ごとに割りながら指数をカウントしていきます。
• 最後のforループで各指数に1を加えて掛け合わせることで、約数の総数である 8 が得られます。

この手法は大きな数に対しても、単純に全約数を列挙して数える方法より高速に動作するため、競技プログラミングなどでもよく使われる定番テクニックです。