Project Euler Problem 21 - ONLY DO WHAT ONLY YOU CAN DO

10000未満の友愛数の和を求めよ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021

$d(n)$ を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, $d(a)=b$ かつ $d(b)=a$ (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので $d(220) = 284$ である.
また, 284 の約数は 1, 2, 4, 71, 142 なので $d(284) = 220$ である.

それでは10000未満の友愛数の和を求めよ.

Amicable numbers

http://projecteuler.net/problem=21

Let $d(n)$ be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If $d(a) = b$ and $d(b) = a$ , where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore $d(220) = 284$ . The proper divisors of 284 are 1, 2, 4, 71 and 142; so $d(284) = 220$ .

Evaluate the sum of all the amicable numbers under 10000.

考え方

自然数 n が、
$n=p^a q^b \cdots r^c$
( $p < q < \cdots < r$ は素数、 $a, b, \cdots c$ は 0 以上の整数)
と素因数分解されるとき、n の約数の個数と約数の総和は、次の公式で与えられる。
約数の個数： $d(n)=(a+1)(b+1) \cdots (c+1)$
約数の総和： $\sigma(n)=\frac{p^{a+1}-1}{p-1} \cdot \frac{q^{b+1}-1}{q-1} \cdot \cdot \cdot \frac{r^{c+1}-1}{r-1}$

たとえば、 $28$ は、 $2^2 \times 7^1$ と素因数分解され、約数は、
$1 = 2^0 \times 7^0$
$2 = 2^1 \times 7^0$
$4 = 2^2 \times 7^0$
$7 = 2^0 \times 7^1$
$14 = 2^1 \times 7^1$
$28 = 2^2 \times 7^1$
で、約数の個数は、 $(2 + 1) \times (1 + 1) = 6$ 個、
約数の総和は
$2^0 \times 7^0 + 2^1 \times 7^0 + 2^2 \times 7^0 + 2^0 \times 7^1 + 2^1 \times 7^1 + 2^2 \times 7^1 = (2^0 + 2^1 + 2^2)(7^0 + 7^1)$
$= \displaystyle\sum_{k=0}^{2}2^k \times \displaystyle\sum_{k=0}^{1}7^k =\frac{2^{2+1}-2^0}{2-1} \times \frac{7^{1+1}-7^0}{7-1}$
$= \frac{8 - 1}{1} \times \frac{49 - 1}{6} = \frac{7}{1} \times \frac{48}{6} = 7 \times 8 = 56$ である。