約数の個数と総和の求め方

約数をひとつずつ探さなくても、素因数分解さえ分かれば、約数の個数と総和は掛け算だけで求まります。$n$ が $n = p^e \times q^f \times \cdots$ と分解できるとします。

約数の個数 $d(n)$ は、各素因数の指数に 1 を足して掛け合わせた値です。

約数の総和 $\sigma(n)$ は、素因数ごとに 1 からそのべき乗までを足し、それらを掛け合わせた値です。

• $n$ — 約数を調べたい整数。1 以上の整数です
• $p$、$q$ — $n$ の素因数
• $e$、$f$ — それぞれの素因数の指数

個数の式は、約数を作る手順を考えると分かります。素因数 $p$ を「0 個から $e$ 個までのどれか」選び、$q$ についても同じように選ぶ。$p$ の選び方は $e + 1$ 通りで、その組み合わせが約数と 1 対 1 に対応します。

例

$n = 36$ とします。$36 = 2^2 \times 3^2$ なので

実際、36 の約数は 1、2、3、4、6、9、12、18、36 の 9 個で、すべて足すと 91 になります。

注意

• 約数の個数には 1 と $n$ 自身も含みます
• 約数がちょうど 2 個なら、その数は素数です（1 と自分自身しか約数を持たないため）
• 個数が奇数になるのは $n$ が平方数のときだけです。ふつう約数は $d$ と $\dfrac{n}{d}$ の 2 つ 1 組で対になりますが、平方数では $\sqrt{n}$ が自分自身と組になり、1 つだけ余るからです。$36 = 6^2$ の個数が 9 と奇数なのはこのためです
• 総和から $n$ を引くと、自分自身を除いた約数の和になります。これが $n$ と等しくなる数を完全数といいます