刚入职没几个月，成为了一坨服务的owner，因巧合触发了陈年代码的bug，导致s0事故，这个锅要背吗

昨天晚上十一点多，我在公司楼下抽烟，手机刷着题，有人在群里问我：“东哥，完美数这题到底难不难？是不是得搞什么高深算发？”我当时困得要死，但是一看是算法题，脑子立马就清醒了。

其实完美数这个东西吧，说白了特别朴素，甚至有点可爱。定义你先记住：一个正整数，把它所有“真因子”（也就是正因子里不包括自己本身那一个）加起来，刚好等于它本身，这个数就叫完美数。

比如 6： 它的正因子是 1、2、3、6，我们只算 1、2、3，和是 1 + 2 + 3 = 6，刚好等于自己，所以 6 是完美数。 28 也是：1、2、4、7、14，和是 1 + 2 + 4 + 7 + 14 = 28。 再往后还有 496、8128……面试一般不会让你背这些，知道前两个就够吹牛了。

怎么用最笨的办法写出来

你想象一下，要判断一个数 n 是不是完美数，最直接的思路就是：把 1 到 n-1 全部枚举一遍，谁能整除 n，就把谁加到 sum 里，最后看 sum 是不是等于 n。

用 Java 写出来大概是这样（这个版本很“直男”，但逻辑一目了然）：

publicclassPerfectNumberDemo1{

// 判断一个数是不是完美数（朴素版）
publicstaticbooleanisPerfect(int n){
if (n <= 1) {  // 1 及以下肯定不是
returnfalse;
        }

int sum = 0;
for (int i = 1; i < n; i++) { // 把 1 ~ n-1 都试一遍
if (n % i == 0) {
                sum += i;
            }
        }
return sum == n;
    }

publicstaticvoidmain(String[] args){
int[] nums = {1, 6, 10, 28, 29};
for (int n : nums) {
            System.out.println(n + " 是否完美数：" + isPerfect(n));
        }
    }
}

这个跑小数据完全没问题，写算法题刚入门的时候用这个也 ok，就是太慢。时间复杂度大概是 O(n)，如果题目说 n 可以到 10^9，那你就准备超时吧。

稍微动点脑子，剪一剪枝

在公司工位上跟我们组小李聊起这题，他一句话点醒我：“你干嘛要从 1 枚举到 n-1 呀？因子是成对出现的啊。”

对吧，比如 28： 2 能整除 28，那它的“配偶”就是 28 / 2 = 14； 4 能整除，那配偶就是 7。

所以你枚举到 √n 就够了，因为每找到一个 i，就能顺带捞出一个 n / i 两个因子，一次赚俩。还有个细节：1 是所有数的因子，可以直接先把 1 加上，从 2 开始枚举。

把这个思路写成 Java 就是这样：

publicclassPerfectNumberDemo2{

// 判断一个数是不是完美数（优化版）
publicstaticbooleanisPerfect(int n){
if (n <= 1) {
returnfalse;
        }

int sum = 1; // 1 一定是因子，先加上
int limit = (int) Math.sqrt(n);

for (int i = 2; i <= limit; i++) {
if (n % i == 0) {
int other = n / i;
                sum += i;
if (other != i) { // 避免平方根重复加
                    sum += other;
                }
            }
        }

return sum == n;
    }

publicstaticvoidmain(String[] args){
for (int n = 1; n <= 10000; n++) {
if (isPerfect(n)) {
                System.out.println("找到完美数：" + n);
            }
        }
    }
}

这里有几个点你在写的时候要注意下：

1. n <= 1 直接 false1 的真因子集合是空集，和是 0，肯定不是完美数。

2. 从 2 枚举到 √n 就够了因子成对出现：(i, n / i)，只要你找到了前半段，后半段白嫖。

3. 平方根要小心重复加比如 n = 16，因子 4 和 16 / 4 也是 4，这个只加一次。

4. sum 初始化为 1不要忘了 1，面试的时候很多人写着写着就把 1 漏了，结果 6 都判不对。

这版复杂度差不多是 O(√n)，代码又不难理解，面试官一般会挺满意。

常见坑，真的是面试高频

那天群里还有个同学提了几个问题，其实都是经常会踩的坑，我顺手给你捋一下：

• 问：负数要不要管？一般题目说的是“正整数”，所以直接 n <= 1 就 false，图省事就行。

• 问：要不要把 n 自己也加进去？不要，我们只加“真因子”，也就是不包含 n 自己那一个。所以 for 循环里不要写 i <= n。

• 问：返回 long 还是 int？题目一般让你判断某个 int 范围内的 n 是不是完美数，用 int 就够； 如果你要玩大数，另说，面试基本用不到那么夸张的。

• 问：要不要去生成前 k 个完美数？如果一定要，那就设个上界，比如在 int 范围内枚举一遍，先打印出来，顺便你也能背几个结果。

写个简单打印示例也行，继续复用上面的 isPerfect：

publicclassPerfectNumberDemo3{

publicstaticbooleanisPerfect(int n){
if (n <= 1) returnfalse;
int sum = 1;
int limit = (int) Math.sqrt(n);
for (int i = 2; i <= limit; i++) {
if (n % i == 0) {
int other = n / i;
                sum += i;
if (other != i) sum += other;
            }
        }
return sum == n;
    }

publicstaticvoidmain(String[] args){
int count = 0;
int n = 2;
while (count < 4) { // 打印前 4 个完美数
if (isPerfect(n)) {
                System.out.println("第 " + (count + 1) + " 个完美数：" + n);
                count++;
            }
            n++;
        }
    }
}

你在本地跑一下，就能看到 6、28、496、8128 这些经典选手。

其实完美数这题吧，本身并不难，难的是很多人一上来就想写什么“高大上算法”，结果越搞越乱，连 6 是不是完美数都算不对。面试官更想看到的是：你能不能把朴素解法先写对，再做合适的优化，边界有没有考虑到，代码是不是干净好读。

行了，我这边咖啡也凉了，你要是哪天在地铁上刷题刷到这道，就把上面的 isPerfect 抄一遍，再自己改改变量名，多写两次就记住了，等会儿我还得去催下我们组那个小李的代码…