# 如何解决LeetCode中完美数的问题 ## 引言 在编程面试和算法练习中，数学相关的问题常常出现。LeetCode上的**完美数（Perfect Number）**问题就是一个典型的数学与编程结合的题目。本文将详细探讨如何高效解决这个问题，涵盖算法思路、代码实现、复杂度分析以及优化方法。 --- ## 问题描述 **完美数**是指一个正整数，它等于除了自身之外的所有正约数之和。例如： - 6的约数为1, 2, 3，且1 + 2 + 3 = 6，因此6是完美数。 - 28的约数为1, 2, 4, 7, 14，且1 + 2 + 4 + 7 + 14 = 28，因此28也是完美数。 **LeetCode问题描述**： 给定一个整数`num`，判断它是否是完美数。如果是，返回`true`；否则返回`false`。 --- ## 初步思路 ### 暴力法 最直观的方法是遍历从1到`num-1`的所有整数，检查是否是`num`的约数，然后累加这些约数，最后判断和是否等于`num`。 ```python def isPerfectNumber(num): if num <= 1: return False sum_divisors = 0 for i in range(1, num): if num % i == 0: sum_divisors += i return sum_divisors == num 问题：
这种方法的时间复杂度是O(n)，对于大数（如num=1e8）效率极低。
数学上，约数是成对出现的。例如，对于num=28： - 1和28（因为1×28=28） - 2和14（因为2×14=28） - 4和7（因为4×7=28）
因此，我们只需要检查到sqrt(num)即可找到所有约数。
优化步骤： 1. 遍历从1到sqrt(num)。 2. 如果i是约数，则将i和num/i加入和（注意避免重复添加sqrt(num)的情况）。
import math def isPerfectNumber(num): if num <= 1: return False sum_divisors = 1 # 1是所有大于1的数的约数 sqrt_num = int(math.sqrt(num)) + 1 for i in range(2, sqrt_num): if num % i == 0: sum_divisors += i counterpart = num // i if counterpart != i: sum_divisors += counterpart return sum_divisors == num 复杂度分析： - 时间复杂度：O(sqrt(n))，显著优于暴力法。 - 空间复杂度：O(1)。
False。num=16时，约数4只需添加一次。def isPerfectNumber(num): if num <= 1: return False sum_divisors = 1 sqrt_num = int(math.sqrt(num)) for i in range(2, sqrt_num + 1): if num % i == 0: sum_divisors += i counterpart = num // i if counterpart != i: sum_divisors += counterpart if sum_divisors > num: # 提前终止 return False return sum_divisors == num 已知的完美数均与梅森素数（Mersenne Primes）相关，其形式为：
[ \text{Perfect Number} = 2^{p-1} \times (2^p - 1) ]
其中，( 2^p - 1 )是梅森素数。
已知的完美数： - 6 (p=2) - 28 (p=3) - 496 (p=5) - 8128 (p=7) - 33550336 (p=13)
对于大数判断，可以直接检查num是否符合上述形式。但需注意： 1. 需要预先生成梅森素数列表。 2. 仅适用于已知的完美数。
代码示例：
def isPerfectNumber(num): known_perfects = {6, 28, 496, 8128, 33550336} return num in known_perfects 适用场景：
如果题目限制num的范围，此方法可达到O(1)时间复杂度。
| 输入 | 预期输出 | 说明 |
|---|---|---|
| 6 | True | 最小的完美数 |
| 28 | True | 第二个完美数 |
| 496 | True | 第三个完美数 |
| 8128 | True | 第四个完美数 |
| 1 | False | 边界值 |
| 2 | False | 非完美数 |
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 暴力法 | O(n) | 小规模数据 |
| 优化遍历法 | O(sqrt(n)) | 通用 |
| 数学性质法 | O(1) | 已知完美数范围 |
解决LeetCode完美数问题的关键在于： 1. 理解约数的成对性质，将时间复杂度从O(n)优化到O(sqrt(n))。 2. 处理边界条件，如num<=1或平方根重复添加。 3. 利用数学性质（如梅森素数）进一步优化（如果允许）。
推荐方法：
在大多数情况下，优化遍历法（O(sqrt(n))）是最平衡的选择，兼顾效率和通用性。
通过完美数问题，我们不仅学习了算法优化，还深入理解了数论在编程中的应用。
练习建议：尝试在LeetCode上提交代码，并对比不同方法的运行时间。 “`
这篇文章涵盖了从暴力法到数学优化的完整解决路径，适合算法学习者深入理解完美数问题。如需调整细节或补充内容，请随时告知！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
