标签: 数学
难度: Easy
对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
给定一个 整数 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
Submission
运行时间: 24 ms
内存: 16.6 MB
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num == 1:
return False
sum = 1
d = 2
while d * d <= num:
if num % d == 0:
sum += d
if d * d < num:
sum += num / d
d += 1
return sum == num
Explain
此题解的核心思想是利用数学方法减少不必要的迭代。对于一个给定的正整数num，如果它是一个完美数，那么它所有的正因子之和（除了它自身）应该等于num。题解中首先排除了1，因为1没有除了自身以外的正因子。接着，从2开始遍历到sqrt(num)，寻找所有可能的因子。如果d是num的因子，则num/d也是num的因子。这样可以在O(sqrt(n))的时间复杂度内找到所有的因子。对于每个找到的因子d，如果d*d不等于num，那么可以将num/d也加入到因子之和中。最后，比较计算出的因子之和与num是否相等，从而判断是否为完美数。
时间复杂度: O(sqrt(n))
空间复杂度: O(1)
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num == 1: # 排除1，因为它没有其他正因子
return False
sum = 1 # 1是所有正整数的因子
d = 2 # 从2开始检查每个数是否为因子
while d * d <= num: # 只需检查到sqrt(num)
if num % d == 0: # 如果d是因子
sum += d # 加上因子d
if d * d < num: # 避免重复加上sqrt(num)时的情况
sum += num / d # 加上配对因子
d += 1 # 检查下一个数
return sum == num # 检查因子之和是否等于num
Explore
遍历到sqrt(num)的原因是因为对任何一个数num而言，如果它可以被d整除（d <= sqrt(num)），那么必定存在一个配对的因子num/d，且这个配对因子必然大于或等于sqrt(num)。这意味着所有大于sqrt(num)的因子都可以在小于等于sqrt(num)时找到其对应的小因子。因此，只需遍历到sqrt(num)，就可以通过d和num/d获得所有因子，不需要遍历到num，这大大减少了计算量。
当`d * d == num`时，意味着d是num的一个平方根，因此d和num/d实际上是同一个数。在这种情况下，如果将num/d加入因子之和，实际上就是重复计算了d。为了避免因子之和被重复计算，只需加入d即可。例如，对于num = 36，当d = 6时，d * d = 36，此时无需再加入36/6=6，因为这会重复计算因子6。
时间复杂度O(sqrt(n))来自于算法中遍历因子的过程。因为算法只检查从2到sqrt(num)范围内的所有整数是否为num的因子，因此遍历的次数大约是sqrt(num)次。由于每次检查操作（包括求余、加法和条件判断）可以视为常数时间操作，所以总的时间复杂度是O(sqrt(n))。这表示算法的执行时间与num的平方根成正比，大大提高了效率，尤其是对于非常大的数。