C++试除法判定质数：从暴力枚举到sqrt(n)优化的算法精讲

1. 项目概述：为什么“试除法判定质数”是算法入门的必修课？

在算法学习和编程面试的征途上，判断一个数是否为质数，几乎是每个C++初学者都会遇到的“第一道坎”。它看似简单，却像一面镜子，能清晰地照出一个程序员对循环、边界条件、算法效率以及数学思维的理解深度。我见过太多朋友，包括当年的我自己，一上来就写个从2遍历到n-1的循环，然后信心满满地提交，结果在力扣（LeetCode）上直接收获一个“超出时间限制”（TLE）。这道题的核心，远不止于写出一个能运行的函数，而在于理解“试除法”背后的优化逻辑，以及如何用C++高效地实现它。

所谓“试除法”，就是尝试用小于该数的整数去整除它，如果都不能整除，则该数为质数。这个定义小学生都懂，但如何在计算机里优雅且高效地实现，就是我们需要深入探讨的。本文将带你从最朴素的思路出发，一步步优化到面试官满意的程度，并深入剖析其中的数学原理和C++实现细节。无论你是正在为蓝桥杯、PAT考试做准备，还是在刷LeetCode为求职热身，掌握这个基础算法的优化之路，都将为你后续学习更复杂的数论算法（如质数筛）打下坚实的基础。

2. 核心思路拆解：从暴力枚举到数学优化

2.1 最朴素的暴力解法及其问题

我们首先从最直观的想法开始：对于一个正整数n，要判断它是否为质数，只需检查在区间[2, n-1]内，是否存在任何一个整数i能整除n（即n % i == 0）。如果存在，n就是合数；如果遍历完整个区间都不存在，n就是质数。

用C++代码表示，核心循环如下：

bool isPrime_naive(int n) { if (n <= 1) return false; // 质数定义大于1 for (int i = 2; i < n; ++i) { if (n % i == 0) { return false; // 发现因子，是合数 } } return true; // 遍历完毕未发现因子，是质数 }

这段代码逻辑完全正确，但它的时间复杂度是O(n)。当n很大时，例如n接近10^9，循环要进行近十亿次，这在任何在线判题系统中都必然会导致超时。因此，这个版本只能存在于教科书的概念讲解中，不具备实际应用价值。

2.2 第一次关键优化：遍历到 sqrt(n)

为什么可以优化？这里涉及一个核心的数论性质：如果n是一个合数，那么它必定有一个不大于其平方根的质因子。

我们来证明一下：假设n是合数，那么它可以表示为两个正整数的乘积n = a * b，且a和b都大于1。如果a和b都大于sqrt(n)，那么a * b > sqrt(n) * sqrt(n) = n，这与n = a * b矛盾。因此，a和b中至少有一个不大于sqrt(n)。我们只需要找到这个较小的因子，就能判定n是合数。

这个性质直接将我们的搜索范围从[2, n-1]缩小到了[2, sqrt(n)]。时间复杂度瞬间从O(n)降到了O(sqrt(n))。这是一个质的飞跃。对于n=10^9，我们最多只需要循环sqrt(10^9) ≈ 31623次，这在现代计算机上瞬间即可完成。

优化后的代码如下：

bool isPrime_sqrt(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); ++i) { // 注意这里是 i <= sqrt(n) if (n % i == 0) { return false; } } return true; }

注意：循环条件i <= sqrt(n)中的等号至关重要。考虑n=4的情况，sqrt(4)=2，如果写成i < sqrt(n)，则循环只会检查i=2，而2 < 2为假，循环根本不会执行，导致错误地将4判定为质数。必须检查到平方根这个边界值。

2.3 第二次优化：处理偶数与步长调整

上面的isPrime_sqrt函数已经足够应对大多数算法题目。但我们还可以进行一次“微优化”，进一步提升效率。

观察一下，除了2以外，所有的偶数都不可能是质数。所以，我们可以在函数开始时先处理掉小于2和偶数（除了2）的情况。然后，在循环中，我们只需要检查奇数因子即可，因为偶数因子必然能被2整除，而我们已经排除了n是偶数（且不等于2）的情况。

优化后的循环可以从3开始，每次步进2（i += 2）：

bool isPrime_optimized(int n) { if (n <= 1) return false; if (n == 2) return true; // 2是质数 if (n % 2 == 0) return false; // 排除所有其他偶数 // 只检查奇数因子，直到 sqrt(n) for (int i = 3; i <= sqrt(n); i += 2) { if (n % i == 0) { return false; } } return true; }

这个优化将循环次数大约减少了一半。虽然时间复杂度依然是O(sqrt(n))，但常数项变小了，在实际运行中会有可观的性能提升，尤其是在需要频繁调用该函数的场景下（例如在质数筛法中辅助判断）。

2.4 关于sqrt(n)的计算优化

在循环条件中直接使用i <= sqrt(n)有一个小问题：sqrt(n)函数本身有一定的计算开销，并且会在每次循环判断时都计算一次。虽然编译器可能会优化，但更稳妥的做法是在循环开始前计算一次平方根并存储。

但这里有一个更优雅且完全等价的写法：将条件i <= sqrt(n)转化为i * i <= n。这样我们就完全避免了调用sqrt函数，也避免了浮点数运算可能带来的精度问题（尽管在整数平方根场景下极少发生）。

最终，我个人最推荐、也最常用的版本如下：

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

这个版本兼具了正确性、高效性和代码的简洁性，是面试和竞赛中的标准写法。

3. 代码实现与细节剖析

3.1 完整可运行的C++程序

理解了原理，我们来看一个完整的程序，它包含一个健壮的isPrime函数和一个简单的测试框架。

#include <iostream> using namespace std; /** * 使用试除法判断一个正整数是否为质数（优化版本） * @param n: 待判断的整数 * @return: 如果是质数返回true，否则返回false */ bool isPrime(int n) { // 边界条件处理 if (n <= 1) return false; // 1及以下的数不是质数 if (n == 2) return true; // 2是唯一的偶质数 if (n % 2 == 0) return false; // 排除所有其他偶数 // 核心试除循环：从3开始，只检查奇数，直到 i*i > n for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) { return false; // 发现一个因子，n是合数 } } // 循环结束未发现因子，n是质数 return true; } int main() { int num; cout << "请输入一个正整数: "; cin >> num; if (isPrime(num)) { cout << num << " 是质数。" << endl; } else { cout << num << " 不是质数。" << endl; } // 附加：输出一定范围内的所有质数，用于验证 cout << "\n--- 验证：1到100之间的质数有 ---" << endl; for (int i = 1; i <= 100; ++i) { if (isPrime(i)) { cout << i << " "; } } cout << endl; return 0; }

3.2 关键代码行解读与注意事项

1. 数据类型选择：函数参数和循环变量使用了int。这适用于大多数情况（int范围约为 -2e9 到 2e9）。如果需要判断更大的数（如long long类型），必须将循环变量i也声明为long long，否则i * i可能会溢出。例如：

   bool isPrime(long long n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (long long i = 3; i * i <= n; i += 2) { // i必须是long long if (n % i == 0) return false; } return true; }

2. 循环条件i * i <= n：这是本算法的灵魂。它确保了循环只在i <= sqrt(n)时执行。当n很大时，i * i可能会溢出吗？对于int类型的n，最大的i是sqrt(INT_MAX) ≈ 46340，i * i的值约为 2.14e9，仍在int的表示范围内，不会溢出。但对于long long类型的n，i最大可达约 3e9，i * i将达到 9e18，这已经超过了long long的最大值（约9.22e18）？不，long long最大值是2^63-1 ≈ 9.22e18，所以9e18仍在安全范围内，但已经非常接近边界。在实际应用中，判断如此大的质数通常不会用试除法，而会使用更高级的算法（如 Miller-Rabin 概率素性测试）。

3. 函数返回值设计：函数返回bool类型，清晰明了。在算法题中，通常要求你实现一个返回bool的函数，而不是直接输出。

4. 性能分析与适用边界

4.1 时间复杂度与空间复杂度

• 时间复杂度：O(sqrt(n))。这是试除法判定质数的时间复杂度上界。最坏情况发生在n是质数时，需要遍历所有i直到sqrt(n)。
• 空间复杂度：O(1)。算法只使用了常数级别的额外空间（几个整型变量）。

4.2 试除法的适用场景与局限

试除法是单点质数判定的经典方法，适用于以下场景：

• 需要独立、偶尔地判断单个或少量数字是否为质数。
• 数字n的大小在10^12以下（sqrt(10^12) = 10^6，百万次循环在现代计算机上可以接受）。
• 作为教学示例，理解质数判定的基本思想。

但是，它也有明显的局限性：

• 效率瓶颈：当需要判断一个区间内大量数字（比如[1, 10^6]）的质数性时，对每个数都使用O(sqrt(n))的试除法，总时间复杂度会接近O(n * sqrt(n))，这是不可接受的。此时必须使用质数筛法，如埃拉托斯特尼筛法（Eratosthenes）或欧拉筛法，它们可以在O(n log log n)甚至O(n)的时间复杂度内筛选出整个区间的所有质数。
• 大数判定：对于超过10^14的大整数，sqrt(n)的循环次数仍然太多。工业级和密码学应用中使用的是基于概率的算法，如Miller-Rabin 素性测试，它可以在多项式时间内以极高的概率给出正确判断。

4.3 与质数筛法的对比

为了让你更清楚何时该用试除法，何时该用筛法，这里做一个简单对比：

简单来说，“需要很多个数，每个只问一次”用筛法；“只需要问一个数，但可能问很多次”用试除法。如果那个“一个数”特别大，试除法也吃力，就要考虑Miller-Rabin了。

5. 常见问题与实战调试技巧

在实际编码和刷题过程中，你肯定会遇到一些“坑”。下面是我总结的几个典型问题和解决方法。

5.1 边界条件处理不全

这是新手最容易出错的地方。

• 问题1：忽略了1和负数。质数定义是大于1的自然数。你的函数必须首先处理n <= 1的情况，直接返回false。
• 问题2：忘记处理数字2。2是唯一的偶质数。如果你在排除偶数时写成if (n % 2 == 0) return false;，那么输入2也会错误地返回false。必须在排除偶数前，单独判断if (n == 2) return true;。
• 问题3：循环边界错误。如前所述，for (int i = 2; i < sqrt(n); ++i)会漏掉平方根这个因子，导致像4、9、25这样的完全平方数被误判为质数。务必使用i * i <= n或i <= sqrt(n)（且注意等号）。

5.2 整数溢出问题

这在处理大数时尤为关键。

• 场景：当n是long long类型，且值很大（例如10^18）时，循环变量i必须也是long long。更隐蔽的溢出发生在循环条件i * i <= n中。当i很大时，i * i的计算结果可能会超出long long的表示范围，发生溢出，导致循环条件判断错误。
• 解决方案：一种安全的写法是将条件转化为i <= n / i。因为n / i这个除法操作不会溢出（只要i不为0），并且i <= n / i在数学上等价于i * i <= n。

  bool isPrime(long long n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (long long i = 3; i <= n / i; i += 2) { // 使用 i <= n/i 避免溢出 if (n % i == 0) return false; } return true; }

  这种写法是处理大数试除时更鲁棒的选择。

5.3 输入输出与性能测试

在在线判题系统（OJ）如 LeetCode 上做题时，通常只需要实现isPrime这个函数。但在自己测试时，你需要编写完整的主程序。

• 多组数据测试：很多题目是要求处理多组输入直到文件结束。你的代码需要适应这种模式。

  int n; while (cin >> n) { // 当成功读入一个n时继续循环 cout << (isPrime(n) ? "Yes" : "No") << endl; }

• 性能测试：你可以写一个简单的脚本，调用isPrime函数判断一个大区间内有多少个质数，并计时。对比优化前后的版本，你能直观感受到从O(n)到O(sqrt(n))的性能飞跃。例如，判断1到100000之间的所有数，朴素版本可能已经慢到无法忍受，而优化版本则瞬间完成。

5.4 算法题中的变形与结合

试除法判定质数很少单独成题，它经常作为其他算法的一个子步骤。例如：

1. 质因数分解：在分解一个合数时，你需要不断地用找到的质因子去除它。而判断用来试除的数i是否为质数，其本质就是试除法。当然，在分解过程中，由于我们是从小到大试除，一旦n % i == 0，这个i必然是质数（因为所有比它小的质数都试过了）。
2. 求约数：求一个数的所有约数时，通常也是遍历1到sqrt(n)，找到所有i和n / i的组合。这和试除法的循环结构一模一样。
3. 孪生质数问题：判断p和p+2是否都为质数，就需要调用两次isPrime函数。

掌握好这个基础的试除法，就像练好了扎马步，后续学习质数筛、Pollard-Rho大数分解等高级数论算法时，你会感到更加得心应手。我个人的体会是，在算法学习初期，不要轻视任何一道“简单”题，把它的每一个优化细节和边界情况都吃透，其价值远大于囫囵吞枣地刷十道难题。这个试除法判质数，就是这样一个完美的起点。