求解整数所有约数之和

问题：求整数所有约数之和。

问题分析

首先，求整数的约数之和，这暗示这是一个正整数。

其次，假设该正整数为 $n$，其约数分别表示为 $d_1, d_2, ..., d_m$ ，则约数和 $S = d_1 + d_2 + ... + d_m$。显然，该题的目的不是得到这个式子，而应该是一般表示形式的简化式。

设：

1. 任意正整数记为 $n$
2. $p_0, p_1, …, p_m$ 为质数
3. $a_0, a_1, …, a_m$ 为正整数

则记 $n$ 的因式分解通式为 $n = p_0^{a_0} · p_1^{a_1} · … · p_m^{a_m}$

$n$ 的约数的因式分解通式为 $p_0^{b_0} · p_1^{b_1} · … · p_m^{b_m}$

其中 $b_0, b_1, …, b_m$ 为以下整数

$$\begin{array}{l} b_0 &= 0, 1, ..., a_0 \\ b_1 &= 0, 1, ..., a_1 \\ &...&\\ b_m &= 0, 1, ..., a_m \end{array}$$

“$n$ 的所有约数和”即是其所有质因数的任一次幂所有组合的和，它等价于下式：

$$\begin{array}{l} S = & (1 + p_0 + p_0^2 + ... + p_0^{a_0}) \\ · & (1 + p_1 + p_1^2 + ... + p_1^{a_1}) \\ · & ... \\ · & (1 + p_m + p_m^2 + ... + p_m^{a_m}) \end{array}$$

这样，每一项乘数都是等比数列，根据求和公式 $1 + x + x^2 + … + x^n = \frac {1 - x^{n+1}} {1 - x}$ 得

$$S = \prod_{k=0}^{m} \frac {1 - p_k^{a_{k+1}}} {1-p_k}$$