零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第九天了，如果能坚持到现在的同学，基本很大程度上可以坚持到最后了，这是 沉没成本 决定的。所以，首先恭喜看到这句话的你。

一、概念定义

  算术基本定理可以描述为：对于每个整数 $n$，都可以唯一分解成素数的乘积，如下：

$$n = p_1p_2p_3...p_k \\ (p_1 \le p_2 \le p_3 \le ... \le p_k)$$

  这里的素数并不要求是不一样的，所以可以将相同的素数进行合并，采用素数幂的乘积进行表示，如下：

$$n = p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k} \\ (p_1 \lt p_2 \lt p_3 \lt ... \lt p_k , \ e_i > 0)$$

二、题目描述

  对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「 完美数 」。给定一个 整数 $n (n \le 10^8)$， 如果是完美数，返回true，否则返回false。

三、算法详解

  要求正因子之和，我们可以把所有不包含自身因子都枚举出来，然后加和，再来和自身作比较。对于一个数 $n$，如果有一个因子 $t$，那么必然 $n$ 能被 $t$ 整除，同样 $n$ 能被 $n/t$ 整除，那么无论 $t$ 和 $n/t$ 哪个大，都可以推导出：$$t \le \sqrt n$$，所以我们可以枚举所有满足条件的 $t$，然后加和所有满足条件的 $t$ 和 $n/t$ 从而得出所有因子的和。

四、源码剖析

bool checkPerfectNumber(int num){
    int i, sum = 0;
    if(num == 1) {
        return false;               // (1)
    }
    for(i = 1; i*i <= num; ++i) {    // (2)
        if(num % i == 0) {           // (3)
            sum += i;
            if(i*i != num)
                sum += num / i;
        }
    }
    sum -= num;                     // (4)
    return sum == num;
}

• $(1)$ 1 的情况需要特殊判断；
• $(2)$ 只需要枚举小于等于 $\sqrt{num}$ 那部分因子;
• $(3)$ 找到因子 $i$ 和 $num/i$，并且累加；
• $(4)$ 根据题意，减去本身；

五、推荐专栏

六、习题练习

请参考原文