0507：完美数

力扣第 507 题

题目

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

给定一个 整数 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

分析

#1

遍历拿到因子即可。注意到除了完全平方数的根以外，因子都是成对出现的，因此只需遍历到 int(sqrt(num))。

1
2
3
4
5

    def checkPerfectNumber(self, num: int) -> bool:
        x = int(sqrt(num))
        s = 1 + sum(i+num//i for i in range(2, x+1) if num%i==0)
        s -= x if x*x==num else 0
        return s == num

56 ms

#2

完美数很少，根据计算在 32 位以内的完美数只有 5 个，因此可以直接判断。

解答

1
2

def checkPerfectNumber(self, num: int) -> bool:
	return num in [6, 28, 496, 8128, 33550336]

36 ms