刷算法题或者做数论相关项目的人基本都绕不过质数这个概念质数判定、分解质因数、筛质数这三件事表面上看起来是三个独立问题实际上背后是同一个数学事实的三种应用——一个合数一定存在一个不超过自身平方根的质因子。这句话一旦吃透三块内容会瞬间串成一条线。这篇就把质数判定、分解质因数、筛质数一次讲透从最直观的暴力写法开始一步步优化到能在竞赛和实际工程里放心用的版本顺便把判断质数 c 优化这个高频搜索词背后真正值得掌握的东西梳理清楚。这篇文章适合处在算法入门到进阶阶段的读者也适合工作中偶尔要处理数论问题的开发同学。你会看到为什么朴素写法会超时、为什么检查到 √n 就够了、6k±1 规律的原理是什么、分解质因数时为什么 n 会越除越小、埃氏筛和线性筛到底差在哪。每个结论我都会先给数学依据再给可运行的 C 代码最后补上实际使用中最容易踩的坑。1. 质数判定从最直觉的写法到 sqrt 边界1.1 暴力枚举为什么会超时质数的定义是大于 1 的自然数中除了 1 和它本身以外不再有其他因数的数。C 里按定义最直接地翻译成代码就是bool isPrime(int n) { if (n 2) return false; for (int i 2; i n; i) { if (n % i 0) return false; } return true; }这个写法逻辑完全正确但在实际场景中几乎必挂。原因是复杂度是 O(n)如果 n 是 10 亿级别循环要执行约 10 亿次单次调用就要跑好几秒更不用说在循环里如果不小心写了sqrt(n)这种每轮都调用的浮点函数性能会雪上加霜。我第一次写质数判定就这样写过后来数据量一大就直接超时才意识到单纯把定义翻译成代码并不够。1.2 一个数学事实决定了优化的天花板判断质数优化的核心依据是这条定理如果 n 是合数那么 n 必然存在一个大于 1 且不超过 √n 的因子。用反证法能直接说明假设 n 是合数且它所有大于 1 的因子都严格大于 √n。那么把 n 写成两个非平凡因子的乘积 n a × b其中 a 和 b 都大于 √n于是 a × b √n × √n n这与 n a × b 矛盾。所以至少存在一个因子不超过 √n。这个结论给了一个非常实用的搜索思路判断质数时只需要在 [2, √n] 这个范围内寻找因子。如果在这个范围内找不到任何能整除 n 的数那么 n 必然是质数。如果把 n 的因数按照大小排成队小的那一半永远不超过 √n大的那一半自然也不用检查了。基于这个定理代码可以优化成bool isPrime(int n) { if (n 2) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; }理论上这个版本已经比最初的暴力写法快了一个数量级但实际工程里我很少用i * i n这种写法原因在下面。1.3 为什么更推荐写 i n / i判断循环边界时常见的写法有三种写法风险i sqrt(n)sqrt 是浮点函数存在精度误差在边界值附近可能判错i * i ni 足够大时乘法可能溢出 int 范围造成死循环或越界i n / i纯整数运算无浮点误差无溢出风险i * i n的问题在于当 n 接近 int 上限时i 只需要到大约 46340i * i 就会逼近 int 的边界一旦 n 是 20 亿级别循环还没判完乘法已经溢出了。用i n / i就没有这个问题因为整数除法永远不会溢出而且它和i * i n在数学上完全等价。从工程角度我的习惯是只要能写成整数不出错的形式就尽量不依赖浮点。i n / i这个写法看起来多了一次除法但现代编译器对 int 除法有很好的优化实际测下来并不比乘法慢多少安全性却高出一大截。2. 质数判定进阶跳过偶数与 6k±1 规律2.1 先排除偶数一步省掉一半循环2 是唯一的偶质数。任一个大于 2 的偶数都一定含有因子 2所以判断质数时可以先把偶数全部排除直接在函数开头做快速筛除bool isPrime(int n) { if (n 2) return false; if (n 2) return true; if (n % 2 0) return false; for (int i 3; i n / i; i 2) { if (n % i 0) return false; } return true; }这个版本把循环步长从 1 改成 2只检查奇数因子理论上循环次数减少了一半。但这还只是热身真正让判断次数再降一个档次的是下面这个规律。2.2 为什么大于 3 的质数都集中在 6 的倍数两侧把任意整数按照对 6 取模的结果分类都能写成六种形式之一6k、6k1、6k2、6k3、6k4、6k5k ≥ 1。逐一看这些形式6k 本身是 6 的倍数显然是合数。6k2 2(3k1)大于 2是偶数合数。6k3 3(2k1)大于 3是 3 的倍数合数。6k4 2(3k2)是偶数合数。六种形式里有四种已经确定是合数只剩下 6k1 和 6k5也就是 6k-1这两种形式有可能是质数。所以任何一个大于 3 的质数一定落在 6 的倍数左右两侧的其中一个位置上。这里要特别注意反过来不成立。形如 6k±1 的数不一定是质数典型的例子是 35 6×6 - 1它就不是质数。6k±1 规律只能用来缩小试除范围不能直接用来判定某个数就是质数。2.3 6k±1 判定法的完整实现有了上面的规律循环步长可以进一步拉大。每轮检查两个候选位置i对应 6k-1i2对应 6k1然后步长加 6进入下一轮。bool isPrime(int n) { if (n 3) return n 1; if (n % 2 0 || n % 3 0) return false; for (int i 5; i n / i; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; }这个版本是单个数质数判定的经典形态。先排除 2 和 3 的倍数再从 5 开始以 6 为步长跳跃检查。理论上试除的候选数只有全部整数的 1/3实际运行起来比单纯排除偶数的版本还要快。对于 n ≤ 10^9 的数值范围这个函数在我的机器上基本是微秒级返回完全够用。2.4 再往上走Miller-Rabin 的简单提及如果待判断的数达到 10^18 这个量级上面所有基于试除的方法都会失效因为循环次数仍然太多了。这时需要 Miller-Rabin 概率性素性测试。它的核心思想是利用费马小定理的推广性质通过几次模幂运算来判断合数单轮判定的正确率是 3/4多轮叠加之后在工程上几乎可以认为是确定的。不过 Miller-Rabin 涉及大量模运算和快速幂代码量明显更大理解门槛也高一些。除非确实在做大数相关的工作入门阶段不建议一上来就啃它先把 6k±1 吃透后续再补完全来得及。3. 分解质因数试除法的核心逻辑与动态边界3.1 唯一分解定理是整块内容的基石分解质因数的数学基础是算术基本定理任何一个大于 1 的整数都能唯一地分解成有限个质数的乘积不考虑顺序的话分解结果是唯一的。比如360 2³ × 3² × 51001 7 × 11 × 13这个定理说明分解质因数的任务其实是在从合数里找出所有以质数为底的因子以及对应的幂次。3.2 标准试除法与除尽为止的细节最直接的做法是从 2 开始从小到大尝试每个整数。一旦发现 n 能被 i 整除就说明 i 是质因子并且要用 while 循环反复除以 i直到 n 不能再被 i 整除为止vectorint factorize(int n) { vectorint factors; for (int i 2; i n; i) { while (n % i 0) { factors.push_back(i); n / i; } } return factors; }这里最关键的一个细节是用 while 而不是 if。原因是同一个质因子可能在 n 中出现多次。比如 360 里 2 出现了三次如果只用 if除以一次 2 之后就移到下一个因子得到的就不是完整的分解结果。while 循环保证把当前质因子彻底除干净剩下的 n 也会随之变小。3.3 动态边界优化看看试除上界如何收缩上面的写法循环条件写成i n对于很大的 n 效率极低。但仔细想一下n 在分解过程中会不断缩小试除的上界也应该跟着缩小。优化的写法是这样vectorint factorize(int n) { vectorint factors; for (int i 2; i n / i; i) { if (n % i 0) { while (n % i 0) { factors.push_back(i); n / i; } } } if (n 1) factors.push_back(n); return factors; }这个版本有两个关键点值得展开。第一循环条件i n / i里藏着动态收缩的效果。初始时循环上界是 √原始n但每除尽一个因子n 就变小循环条件中的n / i也跟着变小循环实际执行的次数往往远少于 √原始n。举一个更直观的例子分解 2^30第一次循环 i2 就把所有 2 除光了n 变成 1循环立刻结束整个过程只做了几次取模而不是真的跑到 √(2^30) 附近。第二循环结束后如果 n 1剩下的这个数必然是质数直接加入答案即可。这一点我在初学时会觉得有点神奇其实证明不复杂假设循环结束后 n 仍是合数那么 n 必有质因子 d 且 d ≤ √n。但由于循环条件是i n / i循环终止时 i 已经超过 √n这意味着 d 一定在前面的循环中被尝试过并且会在 while 循环里被除尽。既然当前 n 依然大于 1只能说明它没有不超过 √n 的因子那它就只能是个质数。3.4 完整分解过程实例用 n 360 手动走一遍i2360 % 2 0while 内 360→180→90→45记录 [2,2,2]n 变为 45。i345 % 3 0while 内 45→15→5记录 [2,2,2,3,3]n 变为 5。i44 5/4不成立循环结束。n5 1把 5 加入。最终结果是 [2,2,2,3,3,5]正好 2³ × 3² × 5 360。这个例子能很清楚地看到动态边界的意义当 n 从 360 缩到 45 再到 5循环的判定范围一直在缩小而不是傻傻地检查到 360。3.5 复杂度分析与最坏情况试除法的理论最坏复杂度是 O(√n)但动态边界让实际运行通常远快于这个上界。最坏情况出现在 n 本身就是一个质数或者 n 只有两个接近 √n 的大质因子。比如 n 999983 × 999979这种数需要从 2 一直试到接近 √n 的位置才能确定没有更小的因子复杂度会贴近 O(√n)。但即便如此对于 10^9 级别的数√n 也就三万多完全能接受。4. 筛质数埃氏筛与欧拉筛深度对比4.1 什么场景下需要筛而不是逐个判断前面讲的质数判定和分解质因数处理的都是单个数字。但如果需求变成判断 2 到 10^7 之间所有数是否为质数每个数单独调用 6k±1 判定总复杂度大约是 N×√N这个数字会非常恐怖。这时候需要用筛法一次性生成整张质数表。筛法的核心思想非常朴素质数的倍数一定是合数。顺着这个方向把所有质数的倍数都标记成合数剩下没被标记的自然就是质数。4.2 埃氏筛直观、好写、够用埃氏筛的流程是从 2 开始扫描遇到一个还没被标记的数就认定它是质数然后把它的倍数全部标记为合数。const int N 10000000; bool isPrime[N 1]; void eratosthenes(int n) { fill(isPrime, isPrime n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } }这段代码有两个细节需要理解到位。第一个细节是内层循环从i * i开始而不是2 * i。原因是 i 的倍数中小于 i² 的那些数比如 2i、3i、……、(i-1)i都含有比 i 更小的质因子它们一定在更早的轮次里被标记过了。举例来说i7 时2×7 在筛 2 的倍数时就已经标记3×7 在筛 3 的倍数时标记5×7 在筛 5 的倍数时标记所以从 49 开始标记就能完全避免重复劳动。这个优化让埃氏筛的实际效率高了不少。第二个细节是外层循环只需要到 √n。因为如果 i √n那么 i² 已经超过 n内层循环没有可标记的对象。埃氏筛的时间复杂度是 O(n log log n)虽然理论上看不是严格的线性但 log log n 增长极慢n 到 10^7 级别时它依然能在一秒内跑完实际工程中绝大多数筛质数的场景用它就够了。4.3 欧拉筛线性筛如何做到每个合数只筛一次埃氏筛有一个固有的浪费同一个合数可能被多个质因子重复标记。比如 12 会被质数 2 标记一次又会被质数 3 再标记一次。数据规模小的时候无所谓但一旦追求极致的效率就需要欧拉筛也叫线性筛来消除这种重复。欧拉筛的核心思想是保证每个合数都只被它的最小质因子筛掉。这样整个筛法操作次数严格为 O(n)。const int N 10000000; bool isComposite[N 1]; vectorint primes; void linearSieve(int n) { for (int i 2; i n; i) { if (!isComposite[i]) { primes.push_back(i); } for (int p : primes) { if (1LL * i * p n) break; isComposite[i * p] true; if (i % p 0) break; } } }这段代码里最需要搞清楚的是if (i % p 0) break;这一行。我在初学时完全看不懂它为什么存在后来才明白它的作用primes 中的质数是从小到大排列的。对于当前的 i依次用 i 乘以小于等于 i 最小质因子的那些质数 p标记 i×p 为合数。关键点在于当i % p 0时p 已经是 i 的最小质因子此时 i×p 的最小质因子也是 p。如果不 break继续取下一个更大的质数 q那 i×q 的最小质因子依然是 p而不是 q。现在用 q 去标记 i×q就违背了每个合数由最小质因子标记的原则而且会导致同一个合数在后续轮次中被重复标记。反过来想每个合数 m 都只会被某个唯一的 i 和它最小质因子的组合标记。并且由于一旦 i 能整除 p 就立刻 break内层循环的平均执行次数非常少整体复杂度才得以保持线性。4.4 两种筛法怎么选筛法时间复杂度代码复杂度额外优势埃氏筛O(n log log n)简单大脑负担小适合大多数场景欧拉筛O(n)中等能同时记录最小质因子后续求欧拉函数、莫比乌斯函数很方便我的经验是如果只是要一张质数表明确用埃氏筛它足够快写起来也难出错。如果后续还要做积性函数相关的事情或者数据规模大到需要严格线性的程度再上欧拉筛。千万不要为了炫技在不需要的场景硬上线性筛代码越复杂出 bug 的概率越高。5. 组合应用质数表加速分解与实战选型5.1 先用筛法拿到质数表再用质数表加速分解如果一个程序需要分解大量数字有一个很实用的组合技巧先筛出 √N 以内的质数表然后所有待分解的数都只试除这些质数而不是从 2 开始逐个整数试除。任意一个不超过 N 的合数它的最小质因子一定不超过 √N所以这张质数表足够覆盖所有情况。int limit sqrt(MAX_N); vectorint primes; // 用埃氏筛或欧拉筛得到 limit 的所有质数省略筛法部分 vectorint fastFactorize(int n) { vectorint factors; for (int p : primes) { if (1LL * p * p n) break; while (n % p 0) { factors.push_back(p); n / p; } } if (n 1) factors.push_back(n); return factors; }这段代码和第三章的试除法几乎一模一样唯一的区别是循环从逐个遍历整数变成遍历质数表。代价是筛表需要额外的预处理时间收益是省去了对合数因子的大量无用取模。假设要分解 1000 个数每个数都从 2 开始试会遇到 4、6、8、9 这些必然不可能整除的合数因子用质数表就直接跳过这些只试 2、3、5、7……整体能省下不少时间。5.2 质数相关代码最常见的几个坑这些是我自己踩过、也在无数同学代码里见过的坑汇总成一张清单建议写的时候逐条对照坑说明忘记特判 11 既不是质数也不是合数很多判定函数只判断n 2就返回没问题但拆解时容易漏i * i n溢出int 环境下 i 到一定大小乘法就溢出用i n / i最稳sqrt(n)浮点误差边界值可能被舍入成错误的整数能用整数运算就不用浮点分解质因数只用 if 不用 while同一个质因子出现多次时就漏了必须用 while 除尽筛法数组越界数组长度是 N1 不是 N下标从 2 开始初始化忘了置 0 和 1 也会错欧拉筛中 i×p 溢出用1LL * i * p n判断不能让 int 乘法在判断前溢出大范围都用朴素判定判断 2 到 N 全部数字时一定用筛法单个数判定才有 O(√n) 的空间5.3 不同任务规模下的算法选型建议根据目标任务的数据规模选型策略完全不同。我给一个自己平时参考的表格任务类型推荐方案总体复杂度单个数 n ≤ 10^9 质数判定6k±1 试除O(√n / 6) 次取模单个数 n ≤ 10^18 质数判定Miller-RabinO(k log³ n)分解单个数 n ≤ 10^9试除法加动态边界O(√n)实际通常更快筛 2 到 10^7 的质数表埃氏筛O(n log log n)筛选算法追求严格线性欧拉筛O(n)分解大量数字先筛质数表再试除预处理 每次 O(质因子数)举个例子N10^7 时用欧拉筛在我本机上的运行时间大约是几十毫秒级别。但如果你对 10^7 个数字逐个使用 6k±1 判定每个数就算只检查到 √n总操作量也会冲上千万级实际耗时完全不是一个量级。数据范围决定思路这句话在质数问题里体现得特别明显。另一个值得记住的经验是不要把质数相关算法孤立地记成代码片段它们的底层是同一套数论原理。6k±1 判定优化来自模 6 剩余类的分析试除法里的动态边界来自合数必有不超过 √n 的质因子线性筛的 break 来自每个合数只被最小质因子标记一次。把这些话说清楚代码写出来就不再是背模板而是真的知道每一步在干什么。判断质数 c 优化的核心从来不是某种神奇的写法而是把数学上可以少检查哪些数字这件事做到极致。从 √n 边界到跳过偶数再到 6k±1每一步都是在数学上缩小搜索空间。分解质因数和筛质数同理。遇到具体问题先算一下数据范围再决定用试除还是筛法最后再考虑要不要引入更高级的工具。基础三件套掌握好了后面再看 Miller-Rabin、Pollard Rho 这些进阶算法理解成本会低很多。