素因数分解を使った約数の個数
正の整数
n の約数の個数を求めるために、単純に 1 から n までの数をすべて走査し、n を割り切れるものをカウントする方法があります。しかし、このやり方は非常に遅くなってしまいます。実は、約数の個数は、
n の素因数を見つけることで効率よく求められます（素因数の探索は 程度の計算量で済みます）。具体的には、ある整数をその素因数の積として表したとき、
各素因数の指数に 1 を加え、それらをすべて掛け合わせると、
n の約数の個数が求まります。この方法を実装するときは、
n の素因数を見つける手順とほぼ同じ要領で行えます。以下のコードは、その一例です（コード自体ではなく、コメント部分のみ翻訳対象です）:n = ...
p, divisors = 1, 1 # 素因数と、約数の個数
while p * p <= n: # p <= sqrt(n) の間くり返す
p += 1 # 各反復で p に 1 を加える
if n % p != 0: # n が p で割り切れなければ何もしない
continue
exp = 0 # 指数をカウントする変数
while n % p == 0: # 割り切れる限り p で割る
n //= p
exp += 1
divisors *= exp + 1 # (指数 + 1) を積にかける
if n > 1: # p が sqrt(n) を超える場合、n は素因数として残っている
divisors *= 2 # 指数が1の素因数を追加
print(divisors)チャレンジ: n の約数の個数を求める
整数
n が与えられたとき、n の約数の個数を求めてください。入力
最初の行に整数
n が 1 つ与えられます (2 ≤ n ≤ )。出力
n の約数の個数を出力してください。例
Input | 入力 |
8 | 4 |
17 | 2 |
2048 | 12 |
48 | 10 |
ボーナス: なぜ素因数の指数に 1 を加え、すべて掛け合わせると約数の個数になるのか？
n の約数を「素因数の組み合わせ」として考えると納得しやすいです。各素因数が何回使われるかは指数で表されますが、0 回使う場合も含める必要があるため、指数に 1 を足して組み合わせの数を数えています。その結果、生じる積が約数の総数を表すことになります。n 自身や 1 もこの方法でしっかりカウントされますし、最終的にはすべての素因数の可能な組み合わせを網羅するため、これが n の約数の個数を正しく示す理由です。Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB