LeetCode-Go 题解 507. Perfect Number：完美数的 Go 实现与数论分析

LeetCode-Go 题解 507. Perfect Number：完美数的 Go 实现与数论分析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 leetcode/0507.Perfect-Number/README.md 为骨架，深入讲解 LeetCode 第 507 题「完美数（Perfect Number）」的两种 Go 解法：基于平方根剪枝的正因子枚举法，以及基于欧几里得–欧拉定理的打表法。读完本文，你将掌握完美数的数学定义、1e8 约束下的高效判定策略，并能直接复用仓库中通过 100% 覆盖率测试的 实现源码 与 测试用例。

一、题目回顾与理解

1.1 完美数的定义

题目原文（来自 leetcode/0507.Perfect-Number/README.md）：

We define the Perfect Number is apositiveinteger that is equal to the sum of all itspositivedivisors except itself.

即：完美数是一个正整数，它等于除自身以外的所有正因子之和。例如：

Input: 28 Output: True Explanation: 28 = 1 + 2 + 4 + 7 + 14

28 的正因子为 1、2、4、7、14、28，除去自身 28 后，其余因子之和恰好等于 28，因此 28 是完美数。

1.2 输入约束

题目给出的约束条件：输入整数n 不会超过 100,000,000（1e8）。这个约束直接决定了两种解法的可行性边界：

• 枚举法需要将因子枚举上界压到√n，否则 O(n) 级别在 1e8 量级会超时；
• 打表法之所以成立，正是因为 1e8 以内的完美数数量极少（仅有 5 个），可以枚举穷尽。

二、解题思路总览

仓库文档 leetcode/0507.Perfect-Number/README.md 的「解题思路」一节给出了两个方向：

1. 按题意直接求解：先获取这个整数的所有正因子，若正因子之和等于原来的数，那么它就是完美数。实现时借助平方根将枚举范围从 O(n) 压缩到 O(√n)。
2. 打表求解：1e8 以下的完美数并不多，就 5 个，直接枚举这 5 个值做等值比较即可，时间开销为 O(1)。

两条路线的本质区别在于：前者是通用算法，适用于任意输入范围；后者是范围特化的查表技巧，在输入有界时具有极致的常数开销。

三、方法一：平方根剪枝的正因子枚举

3.1 核心源码

仓库中的实现位于 507. Perfect Number.go，代码如下：

package leetcode import "math" // 方法一 func checkPerfectNumber(num int) bool { if num <= 1 { return false } sum, bound := 1, int(math.Sqrt(float64(num)))+1 for i := 2; i < bound; i++ { if num%i != 0 { continue } corrDiv := num / i sum += corrDiv + i } return sum == num }

3.2 逐行原理分析

第 7-9 行：特判num <= 1。完美数定义为正整数且等于除自身外所有正因子之和。1 的因子只有自身，除去自身后因子集为空，和为 0，不等于 1；0 与负数更不符合「正整数」前提，因此直接返回false。

第 10 行：初始化因子和与枚举上界。sum初始化为 1，因为任何大于 1 的正整数都必含因子 1（且 1 ≠ num，符合「除自身以外」的要求）。bound = int(math.Sqrt(float64(num))) + 1是枚举上界，这是本方法的核心优化点：

• 对于任意正整数 num，若i是 num 的因子，则num / i也必然是 num 的因子；
• 因子成对出现(i, num/i)，其中较小者必然不超过√num；
• 因此只需枚举2 ≤ i ≤ √num的整数，即可覆盖除 1 和 num 之外的全部因子对，复杂度由 O(n) 降为 O(√n)。

第 11-14 行：配对累加。当num % i == 0时，i与corrDiv := num / i是一对因子，同时累加进sum。以 28 为例：枚举 i = 2（因子对 2、14）、4（因子对 4、7），再加上初始的 1，sum = 1 + (2+14) + (4+7) = 28。

第 15 行：判定。若因子之和等于原数，返回true，否则false。

3.3 边界情况说明

• 当num是完全平方数时（如 36），i = √num这一轮会出现corrDiv == i，代码会累加两次同一个因子（sum += corrDiv + i等价于加了 2 倍）。然而 36 本身不是完美数，这种重复累加不会导致误判为完美数，因为平方数（n ≥ 2）的因子和必然小于等于自身的情况并不会因此改变结论；而真正的完美数中只有 1 是平方数但不满足num > 1的条件。从结果正确性看，该实现通过了仓库全部测试用例（见下文第五节）。
• 该实现刻意不把num自身加入sum（枚举从 i = 2 开始，bound 取√num + 1，num本身远超枚举范围），天然满足「除自身以外」的题设。

四、方法二：打表法

4.1 核心源码

// 方法二 打表 func checkPerfectNumber_(num int) bool { return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336 }

4.2 打表法的数学依据

打表之所以可行，背后是经典的欧几里得–欧拉定理：偶完美数可以写成2^(p−1) × (2^p − 1)的形式，其中2^p − 1是梅森素数。1e8 以内恰好存在 5 个完美数：

这与仓库文档「1e8 以下的完美数其实并不多，就 5 个」的描述完全吻合。由于题目约束n ≤ 1e8，将上述 5 个值逐一比较即可完成判定，时间复杂度为 O(1)，空间复杂度为 O(1)，是常数级别的查表操作。

4.3 两种方法的适用场景对比

五、测试用例与覆盖率验证

仓库为本题提供了完整的测试文件 507. Perfect Number_test.go，采用「参数-答案」表驱动结构：

qs := []question507{ { para507{28}, ans507{true}, }, { para507{496}, ans507{true}, }, { para507{500}, ans507{false}, }, { para507{1}, ans507{false}, }, }

测试覆盖了以下关键场景：

• 28→true：题目给出的标准示例，验证枚举法因子配对逻辑；
• 496→true：第三个完美数，同时验证打表法命中；
• 500→false：非完美数的负例，覆盖枚举完整循环后判false的分支；
• 1→false：边界输入，验证num <= 1特判分支。

测试主体遍历用例并依次调用checkPerfectNumber(p.num)与checkPerfectNumber_(p.num)，同时确保两种解法都被执行到。从仓库根目录的 coverage.txt 可以确认，507. Perfect Number.go中第 6-24 行的两个函数均有对应的覆盖率记录条目，与仓库「100% test coverage」的整体目标一致。

本地运行该用例验证方式：

go test ./leetcode/0507.Perfect-Number/... -v

若需生成全仓库覆盖率报告，可参考仓库根目录的 gotest.sh 脚本（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...）。

六、复杂度与工程实践小结

• 方法一：枚举范围被平方根剪枝压缩到√n，时间复杂度 O(√n)，在 1e8 约束下最多约 1e4 次取模运算，毫秒级完成；空间上仅使用常数个变量。
• 方法二：5 次等值比较，理论最优，是「约束已知 + 答案有限」类问题的通用套路——先穷举小范围答案，再以查表换取常数时间。

在 LeetCode-Go 仓库中，本题归类于 Easy 难度（见 README.md 题目索引中 0507 一行）。值得留意的是打表法在工程上的可迁移性：当题目输入范围有限、候选答案可枚举穷尽时（例如「丑数」、固定进制转换等），预计算答案表往往是最简单且最可靠的优化手段；而枚举法作为面试考察点，重点在于能否写出「因子成对、取√n为上界」的剪枝代码。两者结合使用（先枚举验证，再打表固化），是本题最完整的解法拼图。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go