約数の総和

概要

2つの整数 があり、 が で割り切れるとき、 を の約数という。ちなみに、 は の倍数という。

例えば は の約数。

ある数の 約数の総和（全ての約数を足した値） は、素因数分解して、素数のブロックの中で約数を足し合わせたものをかけることで、求めることができる。

例

を素因数分解すると、 となるので、 の約数の総和は、

と求めることができる。これはすなわち、 の約数

を足した値となっている。（時間が有り余っている人は計算してみよう）

補足

なぜこの式で答えが出るかを、上の例で証明すると、 の約数については、

素因数 の使い方が 通り：

素因数 の使い方が 通り：

素因数 の使い方が 通り：

その掛け合わせた組み合わせが約数となるので、約数の個数は

ある。ここで、上の求めた式

を展開してみると、 個の項の一つ一つが、上の組み合わせた 個の約数になっていて、それらが足される形が出てくることが確認できる。