今天照惯例刷 LeetCode 的每日一题看到 1390“四因数”的时候我第一反应是这不就是个循环套循环的简单题吗结果把几个边界用例跑完才发现题目里藏着的数学判断比表面看起来要微妙得多。如果你也在纠结为什么8是符合条件的四因数、4却不是以及为什么有些人能用质数筛把解法优化到接近线性那这篇笔记应该能帮你把思路一次理顺。这道题非常适合用来巩固“因数个数公式”和“质因数分解”这两块基础同时也能暴露不少暴力枚举时容易踩的雷。无论你是刚开始刷题的新手还是已经刷了三四百题、想找点数学题练手的老炮都值得花几分钟把它彻底吃透。1. 先别急着写循环把“四因数”三个字翻译成数学语言1.1 原题到底要我们算什么LeetCode 1390 的原题描述非常简短给你一个整数数组nums返回该数组中所有恰好有四个正因数的整数的各因数之和。如果不存在这样的整数就返回0。官方示例是输入nums [21, 4, 7] 输出32原因很简单21的因数是1, 3, 7, 21正好 4 个因数和是1 3 7 21 324的因数是1, 2, 4只有 3 个不参与计算7的因数是1, 7只有 2 个不参与计算所以答案就是32。这里有个特别容易忽略的点题目说的是“因数”不是“质因数”。1和这个数本身都算因数任何正整数都至少有这两个因数。很多第一次做这道题的人会把因数直接想成质因数然后看到7只有一个质因数就以为它符合条件——但7只有两个正因数直接出局。1.2 最容易误解的三个点我复盘了自己和评论区里其他人踩过的坑基本集中在三个地方把因数个数和质因数个数搞混。因数包含 1 和自身质因数则必须是质数。例如12的质因数只有2和3但它的因数是1, 2, 3, 4, 6, 12一共 6 个。以为“两个质数相乘”就一定恰好四个因数忽略p * p的情况。p * q如果p ! q确实有且仅有四个因数但如果p q比如4 2 * 2它的因数是1, 2, 4只有 3 个。这是这道题最大的陷阱。枚举到平方根时把同一个因数算了两次。比如n 16在i 4时4和16 / 4 4是同一个因数如果代码里不判断i n / i就会把 4 算两次因数个数变成 5 个结果自然错得离谱。记住这三点后面的代码就不会出现低级失误。1.3 “恰好四个”的深层含义四个因数听起来很简单但如果把“因数个数”的定义再往深挖一层你会发现它本质上描述了一个数唯一的分解结构。设正整数n的标准分解式为n p1^a1 * p2^a2 * ... * pk^ak那么n的正因数个数公式是d(n) (a1 1) * (a2 1) * ... * (ak 1)这个公式的直觉理解是每个质因数pi都可以选0到ai次所以有ai 1种选择方式乘法原理一乘就是总因数个数。要满足d(n) 4乘积只有两种可能(3 1) 4 —— 只有一个质因数指数为 3 (1 1) * (1 1) 4 —— 有两个质因数指数都为 1前者对应n p^3后者对应n p * qp和q是不同质数。这才是“恰好四个因子”真正的数学结构也是后续所有高效解法的出发点。2. 因子个数公式这道题的真正考点2.1 因数个数公式的推导与直觉很多人记不住因子个数公式是因为没有真正理解它。我习惯用一个“组合选择”来类比想象一个自动售货机里面每种饮料都有固定的库存量你要组装一箱饮料。对每个质因子p它在因数里出现的次数可以是0次、1次、……一直到a次一共a 1种选择。不同质因子的选择彼此独立相乘就是所有可能的因数组合。比如72 2^3 * 3^2因数个数就是(31)*(21) 12。你可以验证一下72的因数确实是 12 个。这道题之所以用得上这个公式是因为题目限制“恰好四个因数”等价于限制分解结构的“形状”而不是真的要求你把每个因数都列出来。2.2 四因数的两种标准形态p^3 与 p*q根据上面的公式四因数只能是这两种形态形态例子因数因数个数p^38 2^31, 2, 4, 84p * qp≠q21 3 * 71, 3, 7, 214注意p^3的因子和可以直接用等比数列求和公式1 p p^2 p^3p * q的因子和就是1 p q p * q一旦判断出某个数是这两种形态之一就能直接套公式求和而不需要再去枚举所有因子。这也是把复杂度从O(√n)降到O(1)的关键。2.3 为什么 p^2 不是四因数这是本道题最经典的认知冲突点。很多人在看到p*q后会觉得“质数相乘 四个因数”于是把4 2*2也当成四因数。但从因数个数公式看4 2^2 d(4) (2 1) 34的因数是1, 2, 4只有三个。类似地9, 25, 49这些质数的平方都只有三个因数统统不符合题意。如果你在代码里只判断“能否分解成两个质因数之积”一定要额外检查这两个质因数是否相同。更稳妥的做法是直接用因子个数公式判断而不是手动处理各种特殊情况。3. 解法演进从暴力试除到线性筛预处理3.1 方案一老老实实枚举因子接到题目最简单粗暴的思路就是对于每个数n枚举所有可能的因数并计数。def sum_four_divisors(nums): ans 0 for n in nums: cnt 0 s 0 i 1 while i * i n: if n % i 0: cnt 1 s i if i * i ! n: cnt 1 s n // i i 1 if cnt 4: ans s return ans这段代码有两个细节值得说循环只需要到√n因为因数是成对出现的。比如21枚举到√21 ≈ 4.58只需要试1,2,3,4发现1和21、3和7两对就拿到了全部四个因数。在平方根位置要特别小心。比如n 16√n 4时i和n // i相等这时只能算一次。所以我在if i * i ! n的条件下才加上另一半因数。复杂度分析数组长度为N最大值是M每个数都要枚举到√M总复杂度是O(N√M)。在 LeetCode 原题N ≤ 10^4、nums[i] ≤ 10^5的量级下这个复杂度完全能过总循环次数大约是10^4 * 316 ≈ 3.16 * 10^6在 Python 里也就是几十毫秒的事。但这个方法有个天花板如果nums[i]达到10^9√M 31623再乘10^4就是3.16 * 10^8次循环Python 基本会超时。所以我更推荐下面这种利用质数筛预处理的做法。3.2 方案二质数表 两种形态直接判断既然四因数只有p^3和p*q两种结构那我们可以先筛出所有可能用到的质数然后对每个数判断是否匹配其中一种结构。先算出数组中最大值max_val筛出所有小于等于max_val的质数如果要做p^3判断最坏需要max_val^(1/3)以内的质数如果要做p*q判断需要max_val^(1/2)以内的质数。简单起见直接筛到max_val也没问题反正数据量不大。判断逻辑def is_prime(n, prime_set): if n 2: return False # 对于小范围直接用质数集合 return n in prime_set def sum_four_divisors(nums): max_val max(nums) # 先做埃氏筛 is_prime_arr [True] * (max_val 1) is_prime_arr[0] is_prime_arr[1] False for i in range(2, int(max_val ** 0.5) 1): if is_prime_arr[i]: for j in range(i * i, max_val 1, i): is_prime_arr[j] False ans 0 for n in nums: # 判断 p^3 root3 round(n ** (1/3)) # 注意浮点误差用 range 从 int 附近检查 if root3 ** 3 n and is_prime_arr[root3]: p root3 ans 1 p p * p p * p * p continue # 判断 p * q found False i 2 while i * i n: if n % i 0: q n // i if is_prime_arr[i] and is_prime_arr[q] and i ! q: ans 1 i q n found True break # 只要能整除就已经找到了一个因子不必继续循环 i 1 return ans这里有个容易被误导的地方while里找到一个因子后break就够了吗不一定。如果n 12当你试到i2时q66不是质数如果break了你会直接认为它不满足条件而实际上12确实不满足所以没问题。但假如n 30i2时q15不是质数i3时q10不是质数i5时q6不是质数也不能满足。看起来break是安全的仔细观察如果一个数能写成两个不同质数的乘积p*q那么当你从小到大枚举i遇到的最小因子一定是其中较小的那个质数p此时q也正好是另一个质数。于是第一次碰到整除时i就是那个较小的质数q一定是质数所以可以安全break。若第一次碰到整除时q不是质数那么这个数一定具有至少三个质因数比如2*3*5或者某个质因数指数超过 1比如2^2*3都不是四因数直接排除即可。这个结论可以进一步归纳为只要第一次整除时i和n//i不是两个不同的质数就可以断定n不是四因数。当然为了代码更通用、更不容易出错我建议你还是走完整因子个数公式路线而不是依赖这种“首因子”特殊性质。3.3 方案三欧拉筛最小质因子一劳永逸暴力枚举的优势是简单缺点是每次判断都要做除法质数表的方案把判断压缩到了两种形态但代码里的首因子break需要额外的数学理解。我最终采用的方案是线性筛 质因数分解它最通用后续遇到任何因子个数问题都能复用。核心思路用欧拉筛预处理出每个数的最小质因子spf[x]。对nums中的每个数x借助spf快速做质因数分解得到(质因子, 指数)的列表。用因子个数公式算出总因数个数只有等于4时才继续。根据1.3中的两种形态直接算出因子和。完整代码如下from typing import List class Solution: def sumFourDivisors(self, nums: List[int]) - int: if not nums: return 0 max_val max(nums) # 欧拉筛求最小质因子 spf [0] * (max_val 1) primes [] for i in range(2, max_val 1): if spf[i] 0: spf[i] i primes.append(i) for p in primes: v p * i if v max_val: break spf[v] p if p spf[i]: break ans 0 for x in nums: if x 1: continue tmp x factors [] # 存储 (质因子, 指数) while tmp 1: p spf[tmp] cnt 0 while tmp % p 0: tmp // p cnt 1 factors.append((p, cnt)) # 计算因子个数 div_cnt 1 for _, exp in factors: div_cnt * (exp 1) if div_cnt ! 4: continue # 两种四因数形态 if len(factors) 1 and factors[0][1] 3: p factors[0][0] ans 1 p p * p p * p * p elif len(factors) 2 and factors[0][1] 1 and factors[1][1] 1: p, q factors[0][0], factors[1][0] ans 1 p q p * q return ans为什么用spf分解会非常快因为每个数在分解时tmp都会以指数级速度变小。最坏情况下比如x是 2 的幂也只需要循环log2(x)次。整个预处理是O(max_val)每个数的分解总复杂度是O(log max_val)整体远优于直接对每个数做√x枚举。4. 边界条件全扫雷1、质数、平方数、大数溢出4.1 1 和质数直接出局1的因数只有1一个显然不符合。在质因数分解方案里如果x 1spf[1]是 0while tmp 1一次都不会进入factors为空div_cnt 1最后div_cnt ! 4自然跳过。但为了代码可读性我仍然显式处理了x 1的情况防止后续访问spf[x]出错。质数只有两个因数同样不符合。不过在分解方案里质数会被正确分解成[(p, 1)]对应因子个数(11)2不会误判。4.2 平方根处重复计数嘴边的低级 bug在暴力枚举方案中最容易错的不是数学判断而是代码里的平方根重复计数。我见过很多新手这样写for i in range(1, int(n ** 0.5) 1): if n % i 0: cnt 2 s i n // i如果n是完全平方数比如n 9在i 3时这段代码会把因数3算两次得到cnt 4从而误以为9是四因数。实际1, 3, 9只有三个因数。所以无论用哪种写法都要在i n // i时特殊处理。如果你直接用因子个数公式这个问题自然消失。这也是我推荐最终方案采用质因数分解的原因之一数学判断用公式比计数循环更稳。4.3 数据范围与溢出问题LeetCode 官方没有给出非常极端的范围但我们要养成好习惯凡是求因子和尽量用long在 Python 中不用操心在 C/Java 中建议用long long。举个例子如果nums[i]最大到10^9p*q的形态中p和q可能是999999937 * 999999937吗不会因为那样p q且同时太小。但假设p和q都接近10^9乘积直接溢出int。所以别在求和时用四字节整型。4.4 实测几个刁钻输入我拿了几个有代表性的用例测试nums [8, 21, 4, 7, 9, 27, 2, 1]8 2^3因数1,2,4,8和 1521 3*7因数1,3,7,21和 324 2^2排除7质数排除9 3^2排除27 3^3因数1,3,9,27和 402质数排除1排除所以期望结果是15 32 40 87。实际跑出来确实是87。这个例子能一次性检验我们对p^3、p*q、p^2、质数、1 这五类数的判断是否正确。5. 最终实现与刷题心得5.1 我的完整可提交代码最终我提交给 LeetCode 的版本就是上面的Solution类没有做特殊裁剪。为了让你直接复制使用我再贴一份精简版from typing import List class Solution: def sumFourDivisors(self, nums: List[int]) - int: if not nums: return 0 max_val max(nums) spf [0] * (max_val 1) primes [] for i in range(2, max_val 1): if spf[i] 0: spf[i] i primes.append(i) for p in primes: v p * i if v max_val: break spf[v] p if p spf[i]: break ans 0 for x in nums: if x 1: continue tmp x factors [] while tmp 1: p spf[tmp] cnt 0 while tmp % p 0: tmp // p cnt 1 factors.append((p, cnt)) if len(factors) 1 and factors[0][1] 3: p factors[0][0] ans 1 p p * p p * p * p elif len(factors) 2 and factors[0][1] 1 and factors[1][1] 1: p, q factors[0][0], factors[1][0] ans 1 p q p * q return ans这个版本不用像暴力法那样对每个数都枚举到平方根在max_val较大时优势尤其明显。如果面试时要求现场写你还可以在说明思路后直接写暴力版面试官一般不会刁难。5.2 举一反三因子个数问题的通用模板做完这道题我最大的收获不是记住了“四因数 p^3 或 p*q”这个结论而是把因子个数的通用判断模板沉淀了下来预处理质数表或最小质因子数组。对每个数做质因数分解。用(指数 1)的乘积算因子个数。如果需要因子和用等比数列公式配质因子指数计算。这个模板可以直接迁移到很多问题比如求因子个数为奇数的数即完全平方数、求所有正因子的和、判断友好数对等等。以后遇到“因数”相关的题目我不会再盲目暴力而是先想能不能从质因数分解下手。5.3 写在最后的小技巧最后分享一个我实际调试时踩出来的小技巧如果你在本地测试n ** (1/3)判断立方数最好多检查一步因为浮点数可能把27的立方根算成2.9999999999999996直接取整就变成 2从而漏掉3^3这个合法情况。在方案二里我用的是round(n ** (1/3))但更安全的做法是用整数二分或者直接枚举到n^(1/3)的整数范围去相乘比对。既然最终方案用了质因数分解就不用再担心这种浮点精度问题了这也是我最后定稿选择线性筛的另一个原因。做这道题的时候我一直提醒自己算法竞赛和面试里最怕的不是不会写代码而是没把“恰好四个因数”这个看似简单的条件理解透。一旦理解了因数个数公式整个问题就从一个“枚举题”变成了“质因数分解题”思路瞬间清晰很多。希望你也能在刷每日一题的过程中慢慢体会到这种“把表面问题翻译成数学结构”的快感。