企业官网建设流程全解析

判断一个数是不是素数，可能是每个学 C++ 的人最早接触的算法题之一。不过这些年我帮人改代码、看别人写的题解，发现这个“最简单的题”里其实藏了不少坑——循环上界写成 n 还是 sqrt(n) 差别很大，6k±1 的优化很多人只会背不会证明，更麻烦的是当 n 接近 int 上限时，一个不小心就翻车。这篇文章就从最朴素的写法说起，一路讲到工程里怎么取舍，适合正在学 C++ 的初学者、准备面试的求职者，以及想把这个老题真正写扎实的开发者。

1. 从第一直觉出发：试除法到底在“试”什么

1.1 最直接的版本：从 2 除到 n-1

判断素数的定义很简单：一个大于 1 的自然数，除了 1 和它本身以外没有其他因数。照着定义写，最暴力的做法就是从 2 一直试除到 n-1，只要中间有一个数能整除 n，那 n 就是合数。

bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; }

这个版本的正确性没有问题，但性能糟糕。假设 n 大约是 10 万，你就要做差不多 10 万次取模运算；n 到 10 亿量级，这个函数跑一次就会让程序有明显的卡顿。所以它只能作为理解逻辑用的教学版，真正写起来必须优化上界。

1.2 把上界收到 sqrt(n)，只需要一个数学上很直观的证明

为什么循环到 sqrt(n) 就够了？因为因子永远是成对出现的。如果 n 有一个因子 a 大于 sqrt(n)，那必然存在另一个因子 b 小于 sqrt(n)，而且 b = n / a。换句话说，只要你从小到大试除，在到达 sqrt(n) 之前就已经把比较小的因子 b 试出来了，根本轮不到更大的 a 出场。

这个证明理解起来很容易，但它能直接帮你把复杂度从 O(n) 降到 O(√n)。n 是 10 亿时，循环次数从 10 亿次降到 31623 次，差距是天壤之别。

bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }

1.3 顺手把偶数处理掉，再省一半时间

除了 2 以外，所有偶数都不是素数。所以完全可以先在开头判断n % 2 == 0，如果不是 2 且能被 2 整除，直接返回 false。接着循环从 3 开始，每次步长加 2，只检查奇数因子。

bool isPrime(int n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i <= sqrt(n); i += 2) { if (n % i == 0) return false; } return true; }

改到这一步，已经是一个能应付大多数题目和面试的版本了。但如果你愿意再往前想一步，还会发现一个更经典的优化：6k±1。它的思路不是玄学，而是基于一个非常朴素的观察，下一节展开说。

2. 步进优化：6k±1 是怎么把循环缩短到三分之一的

2.1 大于 3 的质数都住在 6k±1 这条街上

把所有整数按照模 6 的余数分类，余数只能是 0、1、2、3、4、5。大于 3 的质数不可能落在余数 0、2、3、4 这几类里：余数是 0 或 2 的话，这个数一定是偶数，能被 2 整除；余数是 3 的话，它一定能被 3 整除。排除掉这些，剩下的只有余数是 1 或 5 的情况。余数 5 等价于 -1，所以大于 3 的质数一定可以写成 6k-1 或 6k+1 的形式。

注意，这个推论是单向的：质数一定落在 6k±1 里，但落在 6k±1 里的不一定是质数，比如 25 = 6×4 + 1 是合数，35 = 6×6 - 1 也是合数。所以它不能替代判断过程，只能帮助我们跳过那些模 6 余数为 0、2、3、4 的“必合数”因子。

2.2 代码只比以前多了两行，步数减少约三倍

实现的方式是从 5 开始，每次步进 6，每一轮检查i和i + 2这两个候选因子。为什么从 5 开始？因为 5 是第一个满足 6k-1 形式的数，前面的 1 不需要试，2、3、4 要么已经在开头处理，要么不可能成为大于 3 的数的因子。

bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

我算过一笔账：n 在 10 亿量级时，sqrt(n) 大约是 31623，6k±1 版本会把它压缩到大约一万多次除法，差不多只有普通 sqrt 版本的 1/3。单次调用可能很难靠肉眼感知差别，但如果你在一个循环里调用几十万次，差别就是几十毫秒和一百多毫秒的区别，放大到限时的场景里就很关键了。

2.3 这段优化在数据量变大后被拉开的实测感受

有段时间我在一个对拍程序里对比朴素版和 6k±1 版，随机生成了一百万个 int 范围内的数，逐个判断。朴素 sqrt 版本跑完要一百多毫秒，6k±1 版本大约四五十毫秒。差距确实存在，但也不是夸张到一个天一个地。所以我的看法是：6k±1 作为面试回答和工程常用写法非常值得掌握，但别指望它让一个本来就写错的程序起死回生——它优化的是常数，不是复杂度。复杂度仍然是 O(√n)。

到这里，函数看起来已经挺漂亮了，但千万不要急着复制走。下一节要讲的是那些真正让“判断素数”这个简单问题变得不简单的边界情况，尤其是溢出和浮点精度问题，我在实际代码里见过太多次了。

3. 一头扎进边界：那些导致判断函数“偶尔失灵”的坑

3.1 输入为 0、1、负数时，先把它拦在门外

数学上，质数的定义是“大于 1 的自然数”，所以 0、1 以及所有负数都不可能是素数。无论用哪个版本，第一行都应该是if (n <= 1) return false;。听起来像废话，但我在不少给新人看的代码里见过漏掉这一行的——输入是 1 的时候，返回结果竟然是 true，因为循环根本没进去。

更隐蔽的问题是函数签名。如果题目要求判断 long long 范围内的数，只写int n会在读取时就截断数据。除非你确定输入一定在 int 范围内，否则建议直接把参数定义成 long long，省掉很多麻烦。

3.2 循环条件写成 i*i <= n，大数下会“刹不住车”

这是本节最想强调的坑。i * i <= n在直觉上很友好，但如果循环变量是 int，当 i 超过大约 46340 时，i * i 的结果就可能溢出 int 的范围。以 int 最大值为例，46341 × 46341 = 2147488281，已经大于 2147483647，在 C++ 里有符号整数溢出是未定义行为，常见环境下实际表现为回绕成负数。

一旦回绕成负数，负数 <= n恒成立，循环就失去了终止条件，i 会一直增大下去，函数可能卡住，也可能返回一个莫名其妙的错误结果。这个 bug 非常难查，因为它只在 n 很大时才发生，普通的随机测试根本测不出来。

我的建议是改成i <= n / i。这个写法用除法替代乘法，彻底避免溢出，同时也不需要引入浮点数。代价是多做几次除法，但对可读性和正确性来说，这点性能损耗完全值得。

3.3 sqrt 的浮点精度问题：能不用浮点就别用浮点

有人习惯先算int bound = static_cast<int>(sqrt(n));再循环到 bound。在 int 范围内，大部分情况下不会有问题，但 double 的精度毕竟有限，当 n 逼近 int 最大值时，sqrt(n) 的结果处于整数边界附近时，很可能因为舍入误差导致 bound 偏小 1，比如科学计算中 sqrt(2147483647) 在某些实现细节下可能得到 46340.999999，强转 int 后就变成 46340，而这恰好足够，因为 46341^2 已经大于 n；但如果换一个更大的 long long 范围，误差导致漏掉真实因子就不是小概率事件了。

工程上最稳的做法就是不用 sqrt，直接用i <= n / i。如果出于可读性非要用 sqrt，我建议算完之后做一次校正，循环到 r 之后再多检查 r+1，保证不漏。不过说真的，在校验n % i == 0的场景里，i <= n / i的表达已经很自然了，不需要绕道浮点。

3.4 单独兜住 2 和 3，防止误伤

6k±1 版本里有一个非常容易踩的细节：开头必须先判断n <= 3 return true，然后才检查n % 2 == 0 || n % 3 == 0。如果把顺序反过来，n = 2 或者 n = 3 会被第二个判断直接打成 false，因为 2 % 2 == 0，3 % 3 == 0。

我在帮朋友调代码的时候遇到过这种情况：他把 6k±1 优化背得很熟，但漏了n <= 3这一行，结果程序前几个测试样例就挂了。调整顺序之后一切正常。这类“先处理特殊情况，再进入主逻辑”的思路，不止在素数判断里重要，很多算法题都靠这个保持边界正确。

把边界问题盘完，当前的 isPrime 已经可以稳定应付单次数判断。但换个场景，如果问题不是“这个数是不是素数”，而是“从 2 到 1000000 有多少个素数”，再优秀的单个判断函数也会因为重复劳动而显得笨重。这时候就该上筛法了。

4. 从单个数到整张表：筛法介入的实际节点

4.1 判断目标从“一个数”变成“一段范围”

单次调用 isPrime，复杂度是 O(√n)，看起来不大，但如果要查一万次，且 n 都在 10^9 量级，累计就是上亿次取模。这种场景下，逐个判断的方案先天吃亏，因为很多合数会被重复试除很多次。正确思路是一次性预处理出一张“素数表”，后续所有查询都变成 O(1) 查表。

筛法就是干这件事的。它把所有候选数放在一块“筛板”上，通过质数的倍数把合数一个个筛掉，剩下的就是素数。

4.2 普通筛法：用一个布尔数组把合数标记出来

先实现一个最经典的版本：开一个vector<bool>，初始全部为 true，0 和 1 置 false；然后从 2 开始，如果当前数字还是 true，说明它是素数，就把它的倍数从 2p 开始全部标记成 false。

这里有个可以顺手做的小优化：标记倍数时从 p² 开始，而不是 2p。原因是比 p² 小的 p 的倍数，一定已经被更小的素数标记过了，比如 2 的倍数、3 的倍数，轮不到 5 再来一遍。这能省掉一部分重复操作。

vector<bool> simpleSieve(int n) { vector<bool> isPrime(n + 1, true); if (n < 0) return vector<bool>(); 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; } } } return isPrime; }

普通筛法的时间复杂度是 O(n log log n)，实现简单，绝大部分刷题场景已经够用。vector<bool>做了位压缩，内存占用只有普通 bool 数组的 1/8，但代价是访问时有位操作开销。如果追求极致性能，可以换成vector<char>，空间稍大但访问更快。个人建议数据范围 10^7 以内用 vector 完全没问题。

4.3 线性筛：让每个合数只被标记一次

普通筛法为什么不是严格的 O(n)？因为同一个合数可能被多个质因子标记。12 会被 2 筛到，也会被 3 筛到；210 会被 2、3、5、7 各筛一次。这种重复在 n 很大的时候会拖慢速度。

线性筛可以把每个合数只被它的最小质因子标记一次，从而把复杂度稳定控制在 O(n)。代码比普通筛法稍复杂，核心在于内层循环和那句break：

vector<int> linearSieve(int n) { vector<bool> vis(n + 1, false); vector<int> primes; for (int i = 2; i <= n; i++) { if (!vis[i]) { primes.push_back(i); } for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; j++) { vis[i * primes[j]] = true; if (i % primes[j] == 0) break; } } return primes; }

关键语句是if (i % primes[j] == 0) break;。它的含义是：当 primes[j] 已经整除 i 时，i × primes[j+1] 的最小质因子应该是 primes[j]，而不是 primes[j+1]，所以没必要继续枚举更大的质数，立刻 break 可以保证每个合数只被筛一次。不理解也没关系，先记住这个 break 是线性筛的灵魂，删掉它的代码就退化成了普通筛法。

4.4 什么时候该筛，什么时候不该筛

我把实践中总结出来的选型标准列成一个表给你参考：

判断“该不该用筛法”，最简单的方法是估算：调用次数 × 单次平均试除次数 是否远大于筛法预处理的耗时。一般来说，只要查询次数达到几百、范围又在千万以内，直接上筛法都是稳赚不赔的。

5. 换个视角看素性判断：工程里的场景与取舍

5.1 素性检测在真实系统里不止一种形态

大多数人和“判断素数”打交道是在刷题或者笔试里，而真实系统里对素数的需求往往更复杂。最典型的是密码学领域，很多公开密钥加密方案需要生成巨大的随机素数，比如几百位十进制数，这时候试除法会慢到完全不可接受，工程上普遍采用的是概率型素性检测算法，它在数学上给一个“极大概率是素数”的结论，配合多轮随机测试，误判概率可以压到几乎为零。

这类算法的细节远超一篇文章能讲完的，但有一个认知值得提前建立：素性判断从来不是“有唯一正确答案”的问题，而是“在误差、速度、确定性之间做权衡”的问题。这也是为什么我不建议初学者一上来就迷信“最快写法”——不同场景的最优解根本不是一个东西。

5.2 一个顺手、稳定的封装函数

结合前面所有讨论，我给出一个比较完整的成品版本，供你直接复制到项目里当工具函数用：

#include <cstdint> bool isPrime(int64_t n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int64_t i = 5; i <= n / i; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

这个版本的参数用了int64_t，循环条件用了i <= n / i，开头处理了 1、2、3 三个特殊情况，基本可以应对 stdout 输入范围内的所有测试。如果你担心代码可读性，可以加一行注释说明 6k±1 的依据。这样别人阅读时不需要去朝鲜式地背结论。

5.3 几个实操中的小经验

先说测试。写完判断函数后，我强烈建议你和暴力版做一次对拍：随机生成十万个 int 以内的数，用朴素版和优化版分别判断，确保结果一致。这一步非常便宜，但能把你从“没注意溢出”“没处理 2”这类隐形 bug 里解救出来。

再说缓存。如果你的程序里反复判断少量固定的大数，可以考虑用一个 hash 集合存下已验证的结果，命中就直接返回。但对随机输入，缓存命中率太低，加缓存反而浪费。最后一点是有关刷题平台的：有些评测环境不开浮点优化，如果你真的用了sqrt且n接近边界，可能测出意想不到的 WA；所以线程安全的写法是，凡是能做到整数判断的地方尽量避免浮点。

从“写出来”到“写得稳”，中间差的不是高级算法，而是把边界条件当成一等公民来对待的态度。判断素数这个题看起来小，但试除法、复杂度优化、溢出防护、筛法选型这些话题全都包含在里面，把它吃透，后续很多数论题都会顺畅不少。