divisor_count … 約数の個数 - Imoのアルゴリズムライブラリ

素因数分解

説明

素因数の発見は順番に探索していく単純な方法。
n=pkqmpn…の約数の個数は(k+1)(m+1)(n+1)…であることを利用して解いている。

計算量

O(N0.5)

使い方

divisor_count(n)でnの約数の個数を返す。

必要なライブラリ

• なし

ソースコード

約数の個数

int divisor_count(int n) {
  int j, c = 1;
  for (int i = 2; i * i <= n; i++, c *= j)
   for (j = 1; !(n % i); j++) n /= i;
  return (1 < n) ? c * 2 : c;
}

確認

なし