企业官网建设流程全解析

LeetCode 每日一题刷到 1390 这道“四因数”时，我以为又是一道纯粹的数学题，结果做下来发现它把因数枚举、边界处理、性能优化全揉在了一起。题面很简单：给你一个整数数组 nums，对数组里每个元素 x，如果 x 恰好有四个因数，就把这四个因数的和累加到答案里，最后返回总和。比如 nums = [21, 4, 7]，21 的因数是 1、3、7、21，恰好 4 个，和为 32，而 4 的因数是 1、2、4 只有 3 个，7 的因数是 1、7 只有 2 个，都不符合条件，所以答案是 32。

这道题比较适合刚接触算法刷题、想巩固数论基础的人。它不需要什么高深技巧，但能把“枚举因数”“质因数分解”“时间复杂度估算”这些基本功串起来，是你从暴力解法走向高效解法的很好过渡。我自己在写题解和重构代码的过程中，踩了几个挺隐蔽的坑，所以这篇把完整思路、数学原理、代码实现、优化方案和调试过程都拆开讲讲。

1. 题目解读与核心思路拆解

1.1 题目到底在问什么

先别急着写代码，把题目要求拆清楚。输入是一个整数数组 nums，输出是所有“恰好有四个因数”的元素，其全部因数之和的累加结果。注意三个关键词：

• 恰好四个因数，多一个少一个都不行。
• 因数必须是正整数，按照数学定义，正因数包括 1 和它本身。
• 累加的是“因数和”，不是“因数的个数”，也不是“符合条件的元素个数”。

很多人第一反应是：那我直接把每个数的所有因数找出来，数一数是不是 4 个，再把它们加起来不就行了？听起来没毛病，但问题很快会暴露：怎么“把所有因数找出来”？

最朴素的做法，从 1 到 x 逐个取模，能整除的就是因数。这个思路在数字小的时候完全没问题，可一旦 x 变大，比如 x = 99991，你就要循环近十万次。如果 nums 数组有一万个元素，最坏情况下要做十亿次取模运算，超时几乎是必然的。

所以这道题真正考的不是“会不会找因数”，而是“能不能少找一些数就判定因数个数”。这就引出了因数成对出现的性质。

1.2 因数成对出现，找到一半等于找到全部

对于任意正整数 x，如果一个数 d 能整除 x，那么 x / d 也一定能整除 x。也就是说，因数总是成对出现的。比如 12 的因数有 1 和 12、2 和 6、3 和 4，三对。

这个性质的价值在于：我们根本不需要从 1 遍历到 x，只需要从 1 遍历到根号 x。遇到一个能整除的 d，就把 d 和 x / d 同时记录下来。因为 d 超过根号 x 之后，x / d 一定小于根号 x，这些配对在之前就已经被发现了。

唯一需要注意的是完全平方数。比如 16，因数有 1 和 16、2 和 8、4 和 4。当 d = 4 时，x / d 也等于 4，这时候不能把 4 记两次，否则因数个数就多算了。这是后面代码里最容易出错的地方，我一开始就漏了这个判断，导致 16、25、36 这类平方数全部统计错误。

1.3 为什么不能盲目暴力

理论上，枚举到根号 x 已经能解决大部分问题，但面试或竞赛场景里，还要看数据规模。假如 nums 长度为 10^4，每个数最大是 10^5，那么枚举到根号 x 的复杂度是 O(n * sqrt(max))，约等于 10^4 * 316 = 316 万次操作，这个量级在主流在线评测系统里完全能过。可如果每个数变成 10^9，sqrt 之后变成 31623，再乘上 10^4 就是 3 亿次，那就很危险了。

所以我在写题解时，把“枚举到根号”作为第一版方案，因为它最容易写对，也最容易理解。但如果想进一步压榨性能，或者应对更大的数据范围，就得走向质因数分解这条路，这个后面单独开一节细说。先掌握枚举法，因为你至少要保证在常规约束下能写出一个不超时、不出边界错误的版本。

2. 核心算法实现与复杂度分析

2.1 枚举到 sqrt(x) 的通用解法

我的第一版实现用的是最常见的枚举因数思路，复杂度 O(n * sqrt(m))，代码也很直白：

class Solution: def sumFourDivisors(self, nums: List[int]) -> int: total = 0 for x in nums: divisor_sum = 0 divisor_count = 0 d = 1 while d * d <= x: if x % d == 0: divisor_sum += d divisor_count += 1 if d != x // d: divisor_sum += x // d divisor_count += 1 d += 1 if divisor_count == 4: total += divisor_sum return total

关键点在于 while 循环的边界条件d * d <= x。为什么不用d <= sqrt(x)？因为浮点数开方会有精度问题，万一遇到大数边界，sqrt可能产生微小误差，导致循环少一次或多一次。用乘法判定更稳，纯整数运算不会出错。

每次找到能整除的 d，我先把 d 加进因数和，计数加一，然后判断 d 和 x // d 是否相等。不相等时才把另一个因数也加进去。这个判断是整道题最容易丢分的地方，漏掉它，完全平方数会变成“因数个数少一个”，比如 16 会统计为 6 个因数，而不是正确的 5 个。

2.2 复杂度分析：为什么 316 万次操作很稳

很多初学者对“复杂度”没概念，我来算一笔账。假设 nums 长度为 n，数组中最大值不超过 M。上面的代码对每个 x，循环次数是 sqrt(x) 次，总循环次数是 sum(sqrt(nums[i]))，上界是 n * sqrt(M)。

按 LeetCode 原题常规约束，假设 n = 10^4，M = 10^5，sqrt(M) ≈ 316，总操作约 316 万次。即使每次循环里还有取模、加法、比较，总共也就几千万条指令，现代 CPU 跑完不到 0.1 秒，实测提交时间在几十毫秒左右，非常稳。

空间复杂度是 O(1)，只用了几个临时变量。

2.3 为什么“恰好四个因数”只有两种形态

其实这道题有个更快的判断方式，知道这个数学结论，代码可以更简洁。设 x 的标准分解式为：

x = p1^a1 * p2^a2 * ... * pk^ak

根据因数个数公式，x 的因数个数为 (a1 + 1) * (a2 + 1) * ... * (ak + 1)。

要让因数个数恰好等于 4，只有两种情况：

第一种：x = p^3，也就是某个质数的立方。此时因数个数是 3 + 1 = 4，四个因数分别是 1、p、p^2、p^3。

第二种：x = p * q，其中 p 和 q 是两个不同的质数。此时因数个数是 (1 + 1) * (1 + 1) = 4，四个因数分别是 1、p、q、pq。

换句话说，恰好有四个因数的数，要么是某个质数的三次方，要么是两个不同质数的乘积。这里有个很容易踩的陷阱：p * p 不满足条件，因为因数只有 1、p、p^2，一共 3 个，不是 4 个。所以平方数不等于四个因数。

这个结论有什么用？如果你不想枚举所有因数，可以先对 x 做质因数分解，然后根据质因数的个数和指数直接判断。如果分解结果是 1 个质数且指数为 3，答案加 1 + p + p^2 + p^3；如果分解结果是 2 个不同质数且指数都是 1，答案加 1 + p + q + p*q；其他情况一律跳过。

3. 优化思路与质因数分解方案

3.1 从因数个数公式到判定优化

虽然枚举到根号已经能过题，但我在写第二版时还是想试试质因数分解的方案，主要目的是提升单个数很大时的鲁棒性。比如 nums[i] 能达到 10^9 或更大时，枚举到根号就变成最多 31623 次循环，如果数组长度也很大，可能会超时。

质因数分解的思路是：对每个 x，从 2 开始逐个试除，统计每个质因数的指数。为了加速试除，同样只需要试到根号 x。如果一个数在试除完后还大于 1，说明它本身是一个大于根号的质因子。

这里需要格外小心两点：一是计数过程不能用集合或列表保存所有因数，否则空间会变大；二是必须区分“同一个质数出现多次”的情况，比如 x = 8 = 2^3，质因数表是 {2: 3}，符合第一种形态。再比如 x = 12 = 2^2 * 3，质因数表是 {2: 2, 3: 1}，因数个数是 3 * 2 = 6，不符合条件。

3.2 质因数分解的实现细节

下面是基于因数个数公式的优化版实现：

class Solution: def sumFourDivisors(self, nums: List[int]) -> int: total = 0 for x in nums: tmp = x factors = {} d = 2 while d * d <= tmp: if tmp % d == 0: cnt = 0 while tmp % d == 0: tmp //= d cnt += 1 factors[d] = cnt d += 1 if tmp > 1: factors[tmp] = factors.get(tmp, 0) + 1 if len(factors) == 1: p, e = next(iter(factors.items())) if e == 3: total += 1 + p + p * p + p * p * p elif len(factors) == 2: vals = list(factors.items()) if vals[0][1] == 1 and vals[1][1] == 1: p, q = vals[0][0], vals[1][0] total += 1 + p + q + p * q return total

这段代码的思路是先分解出所有质因子及指数，再根据因数个数公式判断因子总数是否为 4。注意我在内层循环里用一个 cnt 记录同一个质数的出现次数，这样后续判断指数是否为 3 或 1 就很方便。

不过我实测之后发现，在 LeetCode 原题的数据规模下，这个优化版的代码反而不如第一版直观，因为每次都要维护一个字典，有哈希开销，实际运行时间并不比枚举法快多少。它的优势主要在于当数据范围放大、枚举到根号已经吃力时，能够显著降低单个数的时间消耗。如果你只是刷这道题，用枚举法就行；如果你想在更大的数据范围下做扩展，质因数分解方案值得掌握。

3.3 两种解法怎么选

我在本地把两种写法都跑了一遍，针对不同数据规模做了简单对拍，结论是这样的：

从复杂度看，两者最坏情况都是 O(sqrt(x))，所以理论上差距不大。但实际运行时，枚举法因为没有额外的哈希结构，常数更小，所以在 LeetCode 1390 的约束下反而更快。质因数分解的价值更多在于“数学通吃”，因为因数个数公式本身能处理任何数量的因数判定，而不只针对“恰好四个”这一种情况。

如果你在面试中遇到这道题，我建议先从枚举法讲起，然后在面试官追问“能不能更快”时，再引出质因数分解和因数个数公式。这样既展示了基础能力，又体现了数学功底。

4. 常见问题与调试实录

4.1 特判 1 和 0 的处理

一开始写代码时，我没有考虑 x = 1 的情况。1 的因数只有 1 一个，显然不符合四因数条件。但如果用枚举法，循环条件直接变成 1 * 1 <= 1，d = 1，能整除，divisor_count 变成 1，不是 4，所以会自动跳过。x = 0 在题目约束里一般不会出现，因为正整数因数定义下 0 没有意义，但如果你在本地测试时遇到，最好明确跳过，避免除零错误。

我在调试时特意加了这样的边界测试：

assert sumFourDivisors([1]) == 0 assert sumFourDivisors([2]) == 0 assert sumFourDivisors([4]) == 0 assert sumFourDivisors([8]) == 0 assert sumFourDivisors([16]) == 0 assert sumFourDivisors([21]) == 32 assert sumFourDivisors([27]) == 40

8 的因数是 1、2、4、8，刚好 4 个，和是 15，等等，这里要重新算一下：8 = 2^3，四个因数是 1、2、4、8，和是 15。27 = 3^3，四个因数是 1、3、9、27，和是 40。这类质数的三次方是最容易遗漏的情况，因为很多人只想到两个质数相乘，忘了三次方形态。

4.2 平方数到底坑在哪里

这道题调试中最大的坑就是完全平方数。假设 x = 16，枚举因数时遇到 d = 4，x // d = 4，两个因子相等。如果代码没有加if d != x // d的判断，就会把 4 加两次，导致因数个数变成 6（1、2、4、4、8、16），和变成 35，严重出错。

更隐蔽的是 36，因数有 1、2、3、4、6、9、12、18、36，一共 9 个，也不是四因数。但因为它存在 d = 6 时 x // d = 6 的情况，如果去重逻辑没写好，计数会错得更离谱。

所以我在调试时养成了一个习惯：构造一批平方数和非平方数混合的测试用例，用枚举法跑一遍，再用质因数分解法对拍结果。如果两种解法输出的答案一致，基本可以认为去重逻辑没问题。

4.3 实际提交中的性能观察

第一次提交时，我用的几乎是裸的暴力枚举，从 1 循环到 x，结果在 LeetCode 上一个比较极端的测试用例上运行时间超过了 1500ms，直接被判定超时。改成枚举到 sqrt(x) 后，提交时间降到了 80ms 左右。

后来我用一个长度为 10000、元素都接近 100000 的数组做本地压测，枚举到 sqrt(x) 的版本只用了约 90ms，质因数分解版本约 120ms。这个差距不大，但足以说明在这种量级下完全没必要上复杂的优化。

如果你发现自己写的代码还是慢，可以检查以下几点：

• 是不是没有用d * d <= x而是反复调用math.sqrt(x)？后者会引入浮点运算开销，虽然不大，但没必要。
• 是不是在循环内部使用了列表收集因数？每收集一个都触发内存分配，会拖慢速度。
• 是不是把循环边界计算放在内层？应该先算好，再循环。

4.4 常见问题速查表

5. 从这道题延伸开去的数论套路

写到这里，想再说一个我刷题时总结的通用套路：凡是让你判断“因数个数”“因数之和”的题目，优先往因数成对、唯一分解定理、因数个数公式这三个方向想。

比如“一个正整数是否恰好有 K 个因数”，通用解法是分解质因数后相乘。如果 K 是 3，那这个数必须是质数的平方；如果 K 是 5，必须是某个质数的四次方；如果 K 是 6，可能是 p^5 或 p^2 * q。这类问题一旦能用质因数角度思考，题目的变化就不大了。

LeetCode 1390 是一个很好的入门样例，因为它的约束条件决定了枚举法也能过，所以对新朋友很友好；同时它又有足够深的数学背景，方便进一步优化和扩展。代码写成什么样不是重点，重点是你能否清晰地解释“为什么恰好四个因数只有两种形态”，这比背模板重要得多。

我自己在刷这道题时最有收获的一点是：不要因为题目简单就跳过边界条件的推演，完全平方数、1、质数的三次方，这几个特判让我在之后做其他因数类题目时少踩了很多坑。如果你也打算坚持每日一题，建议每道题做完后都问自己一句：这个题的核心数学性质是什么？边界条件在哪？是否有比标准解法更本质的规律？这样刷十道，比盲目刷五十道有价值得多。