刷算法题或者做数论相关项目的人，基本都绕不过质数这个概念：质数判定、分解质因数、筛质数这三件事，表面上看起来是三个独立问题，实际上背后是同一个数学事实的三种应用——一个合数一定存在一个不超过自身平方根的质因子。这句话一旦吃透，三块内容会瞬间串成一条线。这篇就把质数判定、分解质因数、筛质数一次讲透，从最直观的暴力写法开始，一步步优化到能在竞赛和实际工程里放心用的版本，顺便把"判断质数 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 <= n | i 足够大时乘法可能溢出 int 范围，造成死循环或越界 |
i <= n / i | 纯整数运算，无浮点误差，无溢出风险 |
i * i <= n的问题在于，当 n 接近 int 上限时，i 只需要到大约 46340，i * 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、6k+1、6k+2、6k+3、6k+4、6k+5（k ≥ 1）。
逐一看这些形式：
- 6k 本身是 6 的倍数，显然是合数。
- 6k+2 = 2(3k+1)，大于 2，是偶数，合数。
- 6k+3 = 3(2k+1)，大于 3，是 3 的倍数，合数。
- 6k+4 = 2(3k+2)，是偶数，合数。
六种形式里有四种已经确定是合数，只剩下 6k+1 和 6k+5（也就是 6k-1）这两种形式有可能是质数。所以任何一个大于 3 的质数，一定落在 6 的倍数左右两侧的其中一个位置上。
这里要特别注意：反过来不成立。形如 6k±1 的数不一定是质数，典型的例子是 35 = 6×6 - 1，它就不是质数。6k±1 规律只能用来缩小试除范围，不能直接用来判定某个数就是质数。
2.3 6k±1 判定法的完整实现
有了上面的规律，循环步长可以进一步拉大。每轮检查两个候选位置：i对应 6k-1，i+2对应 6k+1，然后步长加 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² × 5
- 1001 = 7 × 11 × 13
这个定理说明，分解质因数的任务其实是在"从合数里找出所有以质数为底的因子，以及对应的幂次"。
3.2 标准试除法与"除尽为止"的细节
最直接的做法是从 2 开始，从小到大尝试每个整数。一旦发现 n 能被 i 整除，就说明 i 是质因子，并且要用 while 循环反复除以 i，直到 n 不能再被 i 整除为止：
vector<int> factorize(int n) { vector<int> 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 在分解过程中会不断缩小，试除的上界也应该跟着缩小。优化的写法是这样：
vector<int> factorize(int n) { vector<int> 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，第一次循环 i=2 就把所有 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 手动走一遍：
- i=2：360 % 2 == 0，while 内 360→180→90→45，记录 [2,2,2]，n 变为 45。
- i=3：45 % 3 == 0，while 内 45→15→5，记录 [2,2,2,3,3]，n 变为 5。
- i=4：
4 <= 5/4不成立，循环结束。 - n=5 > 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 更小的质因子，它们一定在更早的轮次里被标记过了。举例来说，i=7 时，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]; vector<int> 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); vector<int> primes; // 用埃氏筛或欧拉筛得到 <= limit 的所有质数，省略筛法部分 vector<int> fastFactorize(int n) { vector<int> 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 质数相关代码最常见的几个坑
这些是我自己踩过、也在无数同学代码里见过的坑，汇总成一张清单，建议写的时候逐条对照：
| 坑 | 说明 |
|---|---|
| 忘记特判 1 | 1 既不是质数也不是合数，很多判定函数只判断n < 2就返回，没问题，但拆解时容易漏 |
i * i <= n溢出 | int 环境下 i 到一定大小乘法就溢出，用i <= n / i最稳 |
sqrt(n)浮点误差 | 边界值可能被舍入成错误的整数，能用整数运算就不用浮点 |
| 分解质因数只用 if 不用 while | 同一个质因子出现多次时就漏了，必须用 while 除尽 |
| 筛法数组越界 | 数组长度是 N+1 不是 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-Rabin | O(k log³ n) |
| 分解单个数 n ≤ 10^9 | 试除法加动态边界 | O(√n)，实际通常更快 |
| 筛 2 到 10^7 的质数表 | 埃氏筛 | O(n log log n) |
| 筛选算法追求严格线性 | 欧拉筛 | O(n) |
| 分解大量数字 | 先筛质数表再试除 | 预处理 + 每次 O(质因子数) |
举个例子，N=10^7 时，用欧拉筛在我本机上的运行时间大约是几十毫秒级别。但如果你对 10^7 个数字逐个使用 6k±1 判定，每个数就算只检查到 √n，总操作量也会冲上千万级，实际耗时完全不是一个量级。数据范围决定思路，这句话在质数问题里体现得特别明显。
另一个值得记住的经验是：不要把质数相关算法孤立地记成代码片段，它们的底层是同一套数论原理。6k±1 判定优化来自模 6 剩余类的分析，试除法里的动态边界来自"合数必有不超过 √n 的质因子"，线性筛的 break 来自"每个合数只被最小质因子标记一次"。把这些话说清楚，代码写出来就不再是背模板，而是真的知道每一步在干什么。
判断质数 c++ 优化的核心从来不是某种神奇的写法，而是把数学上"可以少检查哪些数字"这件事做到极致。从 √n 边界到跳过偶数再到 6k±1，每一步都是在数学上缩小搜索空间。分解质因数和筛质数同理。遇到具体问题先算一下数据范围，再决定用试除还是筛法，最后再考虑要不要引入更高级的工具。基础三件套掌握好了，后面再看 Miller-Rabin、Pollard Rho 这些进阶算法，理解成本会低很多。
