Perfect Number
n 的真因数是小于 n 本身的正因数。完全数等于它所有真因数之和：6 = 1 + 2 + 3。给你一个正整数 n。如果 n 是完全数，返回 true，否则返回 false。
函数
- ninteger
- 要测试的正整数
- 返回值boolean
- 如果 n 等于它的真因数之和，则为 true；否则为 false
约束条件
1 ≤ n ≤ 108
示例
- 输入
- n = 28
- 输出
- true
- 解释
28的真因数是1、2、4、7和14。它们的和是28，所以28是完全数。
- 输入
- n = 12
- 输出
- false
- 解释
12的真因数是1、2、3、4和6。它们的和是16，超过了12。
- 输入
- n = 1
- 输出
- false
- 解释
1没有任何真因数，所以总和是0，不是1。
进阶
每个偶完全数都具有 2^(p-1) × (2^p-1) 这种形式，其中 2^p-1 是素数。你能用这个公式列出所有小于 10^8 的完全数，而不必逐个测试吗？
提示
逐个打开提示，每个都会多透露一点。
写出
28的真因数。如果只查看不超过5的数字，你会找到其中哪些？约数成对出现：如果
d能整除n，那么n / d也能整除n。每对约数中至少有一个不大于√n。将总数设为
1，当n == 1时返回false，然后从2开始循环遍历d，直到d * d ≤ n。将d和n / d加起来，但如果它们相等，只加一次。
题解
将所有候选除数一直检查到 n / 2，当 n = 10^8 时需要进行 5 × 10^7 次除法。除数会成对出现，且每对除数的乘积为 n，因此只需搜索到 √n，大约需要 10^4 步，然后将每对除数的两个数都加上。
将所有真因数相加
结果正确，但无法在最大的测试中运行完毕
思路
按照定义，尝试从 1 到 n / 2 的每个 d，并把能整除 n 的数加起来。对于 28，这样会得到 1、2、4、7 和 14。真因数不会大于 n / 2，因为这样得到的商至少为 2。这个上限也适用于 n = 1：循环运行 0 次，总和保持为 0。
将范围减半不会改变增长趋势。对于任何输入，无论它是不是因数，循环都会运行 n / 2 次。
算法
- 将
total设为0。 - 让
d从1循环到n / 2。 - 如果
n % d == 0，就将d加到total中。 - 返回
total == n是否成立。
def isPerfect(n):
total = 0
# No proper divisor of n is larger than n / 2.
for d in range(1, n // 2 + 1):
if n % d == 0:
total += d
return total == n收集不超过平方根的因数对
思路
当 d 能整除 n 时，n / d 也能整除 n：对于 28，因数对为 1 × 28、2 × 14 和 4 × 7。每对中至少有一个数不大于 √n，因为两个大于 √n 的数相乘会大于 n。因此，搜索到 √n 就能找到每一对因数各一次，然后把两个数都加起来。
因数对 1 × n 会包含 n 本身，而它不是一个真因数，所以把总和初始值设为 1，并从 2 开始搜索。平方根会与自身配对，因此只计数一次。将边界写成 d * d ≤ n，以便使用整数；对于 n = 10^8，循环会在 d = 10^4 时停止。
算法
- 如果
n == 1，返回false。 - 将
total设为1，将d设为2。 - 当
d * d ≤ n时：如果d能整除n，就加上d；如果n / d与d不同，也加上n / d。 - 将
d增加到下一个值。 - 返回
total == n是否成立。
def isPerfect(n):
if n == 1:
return False
total = 1 # 1 divides every n > 1; n itself does not count
d = 2
while d * d <= n:
if n % d == 0:
total += d
partner = n // d
if partner != d: # a square root pairs with itself: add it once
total += partner
d += 1
return total == n
易错点和边界情况
- 通过
1 × n这对因子把n本身也算进去。这样每个和都会大于n：28的因子和变成了56。 - 把
1视为完美数。如果总和从1开始，输入1会满足1 == 1，但它的真因子之和是0。 - 把平方根加了两次。
16的真因子之和是15；把4加两次后，结果变成了19。 - 当
d * d < n时继续循环。这样会跳过平方根，因此永远不会把16的4计入总和。 - 根据浮点平方根确定上限。使用单精度时，完全平方数的平方根可能会小 1，从而漏掉一个因子。
常见问题3
检查一个完全数的时间复杂度是多少？
收集到 √n 为止的因数对需要 O(√n) 时间和 O(1) 空间，对于 n = 10^8，大约需要 10^4 步。测试到 n / 2 为止的每个候选数需要 O(n) 时间，对于相同的输入，大约需要 5 × 10^7 步。
存在奇完全数吗？
没人知道。到目前为止，发现的所有完全数都是偶数，搜索也已经排除了小于 10^1500 的奇数完全数，但还没有证明表明奇数完全数不可能存在。你的函数必须根据定义运行，而不能猜测输入是偶数。
完全数、盈数和亏数有什么区别？
比较真因数之和与这个数。两者相等就是完全数，例如 28。真因数之和更大就是盈数，例如 12，它的真因数之和为 16。真因数之和更小就是亏数，例如所有素数，它们唯一的真因数是 1。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPerfect(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 28
预期输出
true