507.完美数

1、题干

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

 

示例 1：

输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 7
输出：false

 

提示：

• 1 <= num <= 108

2、解题思路

在区间 [ 1,$\sqrt{num}$ ] 中找 $num$ 的因子i，是因子则累加i + num / i（i=1时只加1），最后判断因子之和是否等于 $num$ 即可。

3、代码

var checkPerfectNumber = function (num) {
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) sum += i + num / i;
    }
    return num === 1 ? false : sum === num;
};

4、困惑

题目比较简单，找一个正整数的所有正整数因子只需要遍历到 $\sqrt{n}$ 的结论也一直记着。如果用数学归纳法，举几个例子很容易推出这个结论。

官解这么说：如果 ${n}$ 有一个大于 $\sqrt{n}$ 的因子 $d$，那么它一定有一个小于$\sqrt{n}$的因子$\dfrac{n}{d}$。也就是说 ${n}$ 的因子总是成对出现。

但是有两个关键问题始终让人很困惑：1、为什么遍历终点是 $\sqrt{n}$，2、因子有没有大于 $\sqrt{n}$ 且未被找到的特例。实际上可以用高中数学做个推导，来解答这些困惑。过程有点繁琐，如果对过程不感兴趣可以直接看最后的结论。

5、推导

假设要找正整数 $n$ 的所有正整数因子 $x$ 和 $y$。（注意：以下推导只考虑正整数范围内的情况）

必然有$xy=n$，移项得到 $y=\dfrac{n}{x}$。

反比例函数

这个函数是不是很眼熟，没错它就是高中数学课本里的反比例函数。以 $y=\dfrac{4}{x}$ 为例，其图形如下：

从上图可以很容易看出，反比例函数上的任意坐标 $(x',y')$ 对应的整数 $x'$ 和 $y'$ 都是 $4$ 的因子。这跟官解所说 ${n}$ 的因子总是成对出现的意思一致。也就是找到一个因子 $x'$ 时，必然找到了另外一个因子 $y'$ 。

反比例函数的对称性

反比例函数图像是以 $y=x$ 为对称轴的轴对称图形（反比例函数对称特性）。以 $y=\dfrac{4}{x}$ 为例，其图形如下：

关于 $y=x$ 对称的两个点，他们的坐标是 $x$ 和 $y$ 互换，即任意坐标 $(x',y')$ 的对称点为 $(y',x')$。例如：从上图很容易看出坐标 $(4,1)$ 关于 $y=x$ 对称的点是 $(1,4)$。

由此可得 $n$ 的任意因子对 $(x',y')$ 具有关于 $y=x$ 对称的性质。

而 $y=x$ 与 $y=\dfrac{n}{x}$ 的交点 $Q$ 的坐标是 $(\sqrt{n},\sqrt{n})$。

最后可得，假设遍历因子时取数自 $x$ 轴，在交点 $Q$ 左上侧出现过的任意点 $(x',y')$（其中 $x'<\sqrt{n}$ 且 $y'>\sqrt{n}$），都会在交点的右下侧以 $(y',x')$ 的形式出现。

也就是说，遍历大于 $\sqrt{n}$ 的因子本质上是在重复遍历小于 $\sqrt{n}$ 的因子，只是把小于 $\sqrt{n}$ 时找到的因子对进行 $x$ 、 $y$ 互换位置而已。

因此遍历到 $\sqrt{n}$ 就能找到所有因子，而且没有大于 $\sqrt{n}$ 而未被找到的特例因子，这也就解释了前文提到的两个困惑。

举个例子

$n=36$ 的因子对是 $(1,36)$ $(2,18)$ $(3,12)$ $(4,9)$ $(6,6)$ $(9,4)$ $(12,3)$ $(18,2)$ $(36,1)$

$n=81$ 的因子对是 $(1,81)$ $(3,27)$ $(9,9)$ $(27,3)$ $(81,1)$

可以发现因子对具有回文特性，这也是反比例函数对称性的体现。另外很容易看出$36$ 和 $81$ 这两个数都只要遍历到 $\sqrt{n}$ 即可找到所有因子。

6、小结

找因子之所以只需要遍历到 $\sqrt{n}$，是因为：

• 因子之间存在反比例函数关系 $y=\dfrac{n}{x}$，所以因子总是成对出现
• 反比例函数关于 $y=x$ 对称，所以所有因子对也关于 $y=x$ 对称
• 而反比例函数 $y=\dfrac{n}{x}$ 图形与对称轴 $y=x$ 的交点是 $(\sqrt{n},\sqrt{n})$
• 所以在反比例函数的图形上，任意处于交点 $(\sqrt{n},\sqrt{n})$ 左上侧的点 $(x',y')$ ，都会在交点的右下侧以 $(y',x')$ 的形式出现（其中 $x'<\sqrt{n}$ 且 $y'>\sqrt{n}$）
• 所以遍历到 $\sqrt{n}$ 就能找到所有因子且不会出现大于 $\sqrt{n}$ 而未被找到的特例因子

也就是说，找因子只需要遍历到 $\sqrt{n}$ 即可，因为遍历大于 $\sqrt{n}$ 的因子本质上是在重复遍历小于 $\sqrt{n}$ 的因子，只是把小于 $\sqrt{n}$ 时找到的因子对进行 $x$ 、 $y$ 互换位置而已。 由于数轴上的数具有连续性（非离散），因此这个结论对于小数也成立。