ある数が正の約数として持つ整数の数

数学 競プロ

x = q^n \times p^m \ldots の時、(ただし、q,pなどはすべて素数)
x の正の約数は (n + 1) \times (m + 1) \ldots となる。

例えば80の約数を見るときに
80 = 2^4 \times 5^1
(4 + 1) \times (1 + 1) = 5 \times 2 = 10
として、80の約数は10個あるのだなと分かる。

素数の組み合わせだけ倍数が存在するため、 x^0 \ldots x^n までの n + 1 となるため。