Nの約数の個数を求めるアルゴリズム

数学約数, 素因数分解, 約数の個数

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数:

  1. N を素因数分解する
  2. それぞれの指数に1を足す
  3. 「2.」で得られたものを全てかけ合わせる

※ 素因数分解のアルゴリズムに関してはこちらを参照

※ 例として、\(120 = 2^3 × 3^1 × 5^1\) の約数の個数は、\((3+1)×(1+1)×(1+1) = 16\) となります。

※ 個数だけではなく、どんな約数があるか全列挙したい場合は、N の約数を全列挙するアルゴリズムを参照してください。

計算量

  • 前処理なしのアルゴリズム
    • 前処理:なし
    • クエリ:\(O(\sqrt{N})\)
  • SPF を利用した前処理ありのアルゴリズム
    • 前処理:\(O(N \log \log N)\)
    • クエリ:\(O(\log N)\)

素因数分解に \(O(\sqrt{N})\) だけ時間がかかります。\(O(N \log \log N)\) での前計算を許せば、SPF を利用して \(O(\log{N})\) で素因数分解ができます。(詳細:素因数分解のアルゴリズム

「指数に1を足して、すべてかけ合わせる」のには N の素因数の種類だけ計算することになるので \(O(\log{N})\) 程度で抑えられ、素因数分解の計算量を超えません。

C++での実装例

以下は、標準入力から整数 N を受け取って、Nの約数の個数を出力するプログラムです。前処理なしでのアルゴリズムで実装しています。

練習問題