判断一个数是不是质数——从最朴素的逐一枚举，一步步优化到只需要检查几次。
质数（也叫素数）是指一个大于 1 的自然数，除了 1 和它本身以外，不能被任何其他正整数整除。比如 2、3、5、7、11、13 都是质数；而 4 = 2×2、6 = 2×3、9 = 3×3 这些能被别的数整除的，叫做合数。
1 的因数只有它自己一个（1），凑不出"两个不同的因数"，所以被单独排除在外，既不算质数也不算合数。判断质数时，n < 2 永远应该直接排除。最直接的想法：从 2 开始，把 2 到 n-1 之间所有的数都拿来试一遍，看 n 能不能被整除。只要找到一个能整除的，n 就不是质数；如果一个都找不到，n 就是质数。
| 1 | bool IsPrime(int n) |
| 2 | { |
| 3 | if (n < 2) return false; // 0、1 都不是质数 |
| 4 | for (int i = 2; i < n; i++) |
| 5 | { |
| 6 | if (n % i == 0) return false; // 找到一个因数，n 不是质数 |
| 7 | } |
| 8 | return true; |
| 9 | } |
这种写法完全正确，但效率不高——如果 n 是质数（比如 n = 37），循环会从 2 一直跑到 36，整整检查 35 次才能确定"一个因数都找不到"。n 越大，要检查的次数也越多，时间复杂度是 O(n)。
其实根本不需要检查到 n-1。关键的发现是：一个数的因数总是成对出现的。如果 a 是 n 的一个因数，那么 n / a 必然也是 n 的因数（因为 a × (n/a) = n）。而这一对因数里，较小的那个一定不超过 √n——如果两个因数都比 √n 大，它们的乘积就会比 n 还大，不可能等于 n。
1 2 3 4）是"较小的那一半"因数，灰色格子（36 18 12 9）是它们各自配对的"较大的那一半"——只要把蓝色这些数检查一遍，灰色的因数自动就被发现了（因为它们是配对出现的），完全不需要单独检查。6 × 6 = 36 正好卡在中间，是这个数的平方根，也是检查范围的终点。| 1 | bool IsPrime(int n) |
| 2 | { |
| 3 | if (n < 2) return false; |
| 4 | for (int i = 2; i * i <= n; i++) |
| 5 | { |
| 6 | if (n % i == 0) return false; |
| 7 | } |
| 8 | return true; |
| 9 | } |
i * i <= n，不直接写 i <= sqrt(n)？sqrt() 函数算出来的是浮点数，存在精度误差——比如某些情况下 sqrt(25) 可能因为浮点误差算成 4.999999998 而不是干净的 5.0，导致循环提前一步结束，漏检了 i = 5 这个本该检查的因数。i * i <= n 全程都是整数运算，不会有任何精度问题，而且比调用 sqrt() 函数更快——这是竞赛代码里的标准写法。n 很大时（比如十万、一百万），这个差距是巨大的：n = 1000000 时，基础写法最多要检查 999999 次，优化后只需要检查约 1000 次，快了近 1000 倍。还能再快一点。上一节提到，除了 2 以外的偶数都不是质数——所以可以先把 n = 2 单独处理掉，再把其余的偶数 n 直接排除。剩下需要循环检查的 n 必然是奇数，而奇数永远不可能有偶数因数（如果一个偶数能整除 n，n 就会是偶数，矛盾）——所以循环里可以直接跳过所有偶数，只检查奇数因数，相当于又把检查次数砍掉了接近一半：
| 1 | bool IsPrime(int n) |
| 2 | { |
| 3 | if (n < 2) return false; |
| 4 | if (n == 2) return true; // 2 是质数（唯一的偶数质数） |
| 5 | if (n % 2 == 0) return false; // 排除其余偶数 |
| 6 | for (int i = 3; i * i <= n; i += 2) // 只检查奇数 |
| 7 | { |
| 8 | if (n % i == 0) return false; |
| 9 | } |
| 10 | return true; |
| 11 | } |
循环的起点从 2 改成了 3，每次增加 2（i += 2）而不是 1，跳过了所有偶数：3, 5, 7, 9, ...。配合前面 i * i <= n 这个边界，整体检查次数又减少了接近一半。
用 n = 37（质数）实际数一数三种写法各需要检查多少次，差距非常直观：
2 检查到 36，整整 35 次；只检查到 √37≈6.08 之后，只需要检查 i=2,3,4,5,6 共 5 次（这里实际只数了 i*i<=37 成立的次数，即 i 取到 6 为止）；再跳过偶数只检查奇数 i=3,5，只需要 2 次就能确定 37 是质数。优化的效果立竿见影。| 写法 | 检查范围 | 时间复杂度 | 说明 |
|---|---|---|---|
| 基础写法 | 2 ~ n-1，逐个检查 | O(n) | 最直观，但 n 较大时很慢 |
| 只检查到 √n | 2 ~ √n | O(√n) | 核心优化，必须掌握 |
| + 跳过偶数 | 3 ~ √n，只取奇数 | O(√n)，常数减半 | 锦上添花，复杂度量级不变但实际更快 |
IsPrime 函数适合"只判断一个数"的场景，每调用一次都要重新计算一遍。但如果题目要求"找出 1 到 100 万之间所有的质数"，对每个数都跑一遍 IsPrime 会非常慢——这种场景下有专门的批量筛法，一次性把一个范围内所有的质数都标记出来，效率比逐个判断高得多。这个技巧叫线性筛，会在模块一的最后一节（1.8）详细介绍。