在算法学习和编程面试中，素数问题是一个绕不开的经典话题。今天，我们将深入探讨如何使用 C++ 解决一个常见的问题：给定一个整数 n，打印从 1 到 n 之间的所有素数。
这听起来像是一个简单的任务，但如果我们不深入思考，很容易写出运行缓慢的代码。在这篇文章中，我们将从最基础的方法出发，逐步优化算法，最终掌握性能极佳的高级筛法。无论你是刚接触 C++ 的新手，还是希望优化代码性能的开发者，这篇文章都将为你提供实用的见解和技巧。
什么是素数？
首先，让我们快速回顾一下定义。素数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。换句话说，它不能被分解为两个更小的自然数的乘积。数字 2 是最小的也是唯一的偶素数，而 1 通常不被视为素数。
问题分析
示例输入 1
n = 10
示例输出 1
2, 3, 5, 7
解释：在 1 到 10 之间，只有这四个数符合素数的定义。
示例输入 2
n = 20
示例输出 2
2, 3, 5, 7, 11, 13, 17, 19
为了解决这个问题，在 C++ 中主要有几种策略。我们将从最直观的方法开始，逐步过渡到最高效的解决方案。
—
方法一：基础试除法
思路解析
最直观的想法是：我们遍历从 1 到 n 的每一个数字，对于每一个数字，我们单独判断它是不是素数。
那么，如何判断一个数 INLINECODE76fddabe 是素数呢？根据定义，如果 INLINECODE1270710f 只能被 1 和它自己整除，那它就是素数。我们可以尝试用 2 到 INLINECODE31c79491 之间的所有整数去除 INLINECODE399d8a7a。只要有一个数能整除它，那就说明它有其他因数，不是素数。如果遍历完所有数都没有找到能整除的，那就是素数。
代码实现
让我们来看看具体的 C++ 代码实现：
// C++ program to print prime numbers from 1 to n
// using the basic Trial Division approach
#include
using namespace std;
// 判断一个数是否为素数的辅助函数
bool isPrime(int num) {
// 1 不是素数，直接返回 false
if (num == 1)
return false;
// 检查从 2 到 num - 1 是否有因数
// 如果 num 能被中间的任何一个数整除，则它不是素数
for (int i = 2; i < num; i++) {
if (num % i == 0)
return false;
}
// 如果循环结束都没找到因数，则是素数
return true;
}
int main() {
int n = 20;
cout << "1 到 " << n << " 之间的素数有: ";
// 遍历 1 到 n 的每一个数字
for (int i = 1; i <= n; i++) {
// 如果当前数字是素数，则打印
if (isPrime(i)) {
cout << i << " ";
}
}
return 0;
}
输出结果：
1 到 20 之间的素数有: 2 3 5 7 11 13 17 19
性能分析
虽然这段代码逻辑清晰，容易理解，但它的效率并不高。让我们来分析一下它的复杂度：
- 时间复杂度： O(n²)。对于外层循环的每一个数字 INLINECODE678cb675，我们最坏情况下要进行 INLINECODE7f9c26bc 次除法运算。当
n比较大时，这个运行时间会显著增加。 - 辅助空间： O(1)。我们只使用了几个变量，没有使用额外的存储空间。
实际应用中的问题
你可能会发现，当 n 超过 10,000 时，程序开始明显变慢。这是因为我们做了很多“无用功”。例如，判断 100 是否为素数时，我们其实不需要检查 50 到 99 这些数字，因为如果能被 50 整除，肯定也能被 2 整除。让我们看看如何优化这一点。
—
方法二：优化的试除法
思路解析
我们可以利用一个数学性质来大幅减少检查范围：如果一个数 INLINECODE931576dc 有因数，那么它至少有一个因数小于或等于 INLINECODE50201918。
这是为什么呢？如果 INLINECODEd2d15c88，且 INLINECODE2d2e91dd 和 INLINECODE4459a6e7 都大于 INLINECODE8f6e1284，那么 INLINECODE1540626c 就会大于 INLINECODEb3484bd4，这是不可能的。因此，我们只需要检查 2 到 √n 之间的数即可。这将内层循环的时间复杂度从 O(n) 降低到了 O(√n)。
代码实现
下面的代码展示了这种优化方法，请特别注意循环条件的改变：
// C++ program to print prime numbers from 1 to n
// using Optimized Trial Division
#include
#include // 用于 sqrt 函数，尽管我们通常用 i*i <= n
using namespace std;
// 优化后的素数判断函数
bool isPrime(int num) {
// 1 不是素数
if (num == 1)
return false;
// 优化：只需检查到 sqrt(num)
// 使用 i*i <= num 比 i <= sqrt(num) 更快，避免了浮点运算
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}
int main() {
int n = 50;
cout << "1 到 " << n << " 之间的素数有: ";
// 遍历范围 1 到 n
for (int i = 1; i <= n; i++) {
if (isPrime(i)) {
cout << i << " ";
}
}
return 0;
}
输出结果：
1 到 50 之间的素数有: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
进一步优化：跳过偶数
除了检查到平方根，我们还可以跳过所有的偶数（除了 2）。因为任何大于 2 的偶数肯定不是素数。在判断时，我们可以先检查 2，然后只从 3 开始，每次加 2（即只检查奇数）。这能将速度再提高一倍。
这是你应该掌握的最佳实践之一：
bool isPrimeBestPractice(int num) {
if (num == 1) return false;
if (num == 2) return true;
// 排除所有大于2的偶数
if (num % 2 == 0) return false;
// 从 3 开始，每次步长为 2
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0)
return false;
}
return true;
}
性能分析
时间复杂度： O(n √n)。对于 INLINECODEedc59093 个数字，每个数字检查成本为 √n。这在处理百万级以下的 INLINECODEc5ca3989 时，表现是可以接受的。
- 辅助空间： O(1)。
这种方法对于单次查询某个数是否为素数非常有效。但是，如果我们需要找出 1 到 n 之间的所有素数，还有没有更快的“批量”处理方法呢？答案是肯定的。
—
方法三：埃拉托斯特尼筛法
思路解析
当我们要找 1 到 n 之间的所有素数时，埃拉托斯特尼筛法 是效率最高的算法之一。它的核心思想不再是“逐个检查”，而是“批量排除”。
算法步骤：
- 创建一个布尔数组 INLINECODEff871d7a，初始化为 INLINECODE791681e8。假设所有数都是素数。
- 标记 INLINECODE7fffb443 和 INLINECODEca5565d3 为
false（因为它们不是素数）。 - 从 INLINECODE094f7e7f 开始（第一个素数），如果 INLINECODE6564a251 仍然为 INLINECODE7e8829e8，则 INLINECODEae0cb1a6 是素数。
- 将 INLINECODEeb3a1f18 的所有倍数（即 INLINECODE178a792d）都标记为
false（合数）。 - 移动到下一个未被标记为 INLINECODE343f45f6 的数字，重复步骤 4，直到 INLINECODEf3a3258b 的平方大于
n。
为什么要从 p² 开始？
在筛法中，当我们处理素数 INLINECODE9997eaf0 时，其实可以从 INLINECODE3ac054ff 开始标记。例如，处理 INLINECODEfdeda7eb 时，INLINECODEb936051d 和 INLINECODE1d908e66 已经在处理 INLINECODE891a7d40 和 INLINECODEe65012b8 时被标记过了。为了避免重复计算，内层循环直接从 INLINECODE96c027aa 开始。
代码实现
// C++ program to print prime numbers from 1 to n
// using Sieve of Eratosthenes
#include
#include
using namespace std;
void printPrimesSieve(int n) {
// 创建一个大小为 n+1 的布尔向量，初始化为 true
// prime[i] 为 true 表示 i 是素数
vector prime(n + 1, true);
// 0 和 1 不是素数
prime[0] = prime[1] = false;
// 遍历从 2 到 sqrt(n)
for (int p = 2; p * p <= n; p++) {
// 如果 prime[p] 没有被改变过，则它是素数
if (prime[p] == true) {
// 将 p 的所有倍数更新为非素数
// 注意：我们从 p*p 开始，因为 2*p 等已经被更小的素数筛过了
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// 打印所有为 true 的数
cout << "1 到 " << n << " 之间的素数有: ";
for (int p = 2; p <= n; p++) {
if (prime[p])
cout << p << " ";
}
cout << endl;
}
int main() {
int n = 50;
printPrimesSieve(n);
return 0;
}
性能分析
筛法的时间复杂度通常被认为是 O(n log log n)，这比之前的 O(n * √n) 要快得多，特别是当 n 非常大（例如 10^7 或更大）时，差异非常明显。
- 时间复杂度： O(n log log n)
- 辅助空间： O(n)。我们需要一个数组来存储标记状态，这是用空间换时间的典型做法。
常见错误与解决方案
在使用筛法时，初学者容易犯一个错误：试图用 INLINECODEbf16492d 并且不进行初始化，或者在超大 INLINECODE8e0d9933 的情况下使用栈内存导致栈溢出。解决方案是始终使用 INLINECODEccda6b90 或动态分配内存，因为 INLINECODE286a8c5b 通常在堆上分配内存，可以处理更大的数据量。
此外，如果你在竞赛或高性能场景下处理极大数据（如 10^8），可以将 INLINECODE6d62db46 改为 INLINECODEea0f72bb 或者 INLINECODE6a39bae8。C++ 标准库中的 INLINECODE6d55d52e 虽然节省空间，但由于其特化机制，访问速度有时不如 vector 或原生数组快。
—
总结与实战建议
我们已经探讨了三种打印 1 到 n 素数的方法。作为开发者，我们应该如何选择呢？
- 试除法（基础版）：仅适用于理解概念或
n极小（< 100）的情况。代码简单但效率低。 - 优化试除法：最通用的单次判断方法。如果你只需要判断某几个特定的数是否为素数（例如判断用户输入的一个密码是否是素数），这是最好的选择。
- 埃拉托斯特尼筛法：处理批量查询（如 1 到 n）的王者。如果你需要预处理一定范围内的所有素数，或者需要进行多次查询，一定要优先考虑这种方法。
最佳实践回顾
- 循环条件：在判断素数时，尽量使用 INLINECODE4742cdd6 而不是 INLINECODE5e73ff87 或
i <= sqrt(n)，以避免不必要的开销。 - 类型选择：注意 INLINECODEabde09ac 的大小，如果 INLINECODE3f5a3d62 超过了 INLINECODE093a5e10 的范围，记得使用 INLINECODE7b0dacdb。
- 代码可读性：即使是简单的算法，也要写好注释。像 INLINECODE86ca01a3 这样的辅助函数能让 INLINECODEceaee4ab 函数逻辑更清晰。
希望这篇文章能帮助你更好地理解 C++ 中的素数处理算法。试着修改代码中的 n 值，观察不同方法的性能差异吧！如果你有更好的优化思路，欢迎继续探索。