针对“输入一个自然数
N
N，求出
1
−
N
1−N 中所有质数”这一问题，虽然可以使用试除法逐个判断，但在需要输出范围内所有质数的场景下，埃拉托斯特尼筛法（Sieve of Eratosthenes） 是最高效且标准的解法。
以下是详细的解题思路、代码实现及优化讲解。
核心算法：埃氏筛法
原理：
创建一个布尔数组 is_prime，初始假设所有数（从2开始）都是质数。
从最小的质数 2 开始，将 2 的所有倍数（4, 6, 8...）标记为合数（非质数）。
找到下一个未被标记的数（即 3），将其所有倍数（9, 15, 21...，注意从
i
∗
i
i∗i 开始优化）标记为合数。
重复上述步骤，直到处理完
N
N
以内的所有数。
最后，数组中仍标记为 true 的下标即为质数。
为什么比逐个试除快？
试除法：对每个数
i
i 都要检查
i
i
次，总复杂度约为
O
(
N
N
)
O(N
N
)。
埃氏筛：通过“批量标记”消除合数，总复杂度约为
O
(
N
log
log
N
)
O(NloglogN)，在
N
N 较大时（如
1
0
6
10
6
或
1
0
7
10
7
）速度优势极其明显。
C++ 代码实现
cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
// 优化IO操作，加速输入输出
ios::sync_with_stdio(false);
cin.tie(NULL);
}
代码关键点解析
数据类型与溢出保护：
在循环条件 i * i <= N 中，如果
N
N 接近 int 的最大值，i * i 可能会溢出。因此建议强制转换为 long long 进行比较：(long long)i * i <= N。
内层循环 j 从 i * i 开始，同样要注意 i * i 不溢出。对于本题常见的
N
≤
1
0
6
N≤10
6
或
1
0
7
10
7
，int 通常足够，但养成习惯很重要。
空间优化：
使用 vector<bool> 是 C++ STL 中的特化版本，每个元素只占 1 bit，非常节省内存。如果
N
N 达到
1
0
8
10
8
级别，vector<bool> 约需 100MB 内存，而 vector<char> 需 100MB，bool 数组可能更多。对于一般竞赛题（
N
≤
1
0
6
N≤10
6
），两者皆可。
输出格式控制：
题目要求“以空格隔开”。通常最后一个数字后面不应有多余空格。代码中使用 first 标志位来判断是否是第一个输出的质数，从而决定前面是否加空格。
效率优化：
IOS::SYNC_WITH_STDIO(FALSE); 和 CIN.TIE(NULL); 可以显著加快 C++ 的输入输出速度，特别是在输出大量数据时（例如
N
1
0
6
N=10
6
时有几万个质数要输出）。
备选方案：试除法（仅适用于极小范围或学习目的）
如果
N
N 非常小（例如
N
<
1000
N<1000），或者你只想练习单个数的判断，可以使用试除法。但对于“求 1-N 所有质数”这类题目，强烈推荐使用筛法。
试除法核心函数参考：
cpp
bool isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
// 只检查奇数因子，且只到 sqrt(n)
for (int i = 3; (long long)i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
在主函数中遍历 2 到 N 调用此函数即可，但效率远低于筛法。
总结
推荐算法：埃拉托斯特尼筛法（Sieve of Eratosthenes）。
时间复杂度：
O
(
N
log
log
N
)
O(NloglogN)。
空间复杂度：
O
(
N
)
O(N)。
注意事项：处理好
0
,
1
0,1 的非质数情况，注意整数溢出，以及输出格式的空格控制。
