埃拉托斯特尼筛法：常用于判断1～n之间的数字是否是质数。
基本原理
- 从2开始，将每个素数的倍数标记为合数
- 未被标记的数就是素数
步骤：
- 初始化1～n之间所有的数字，默认“是”质数
- 从i=2开始遍历，只要
i*i<=n就继续向后遍历，如果当前数字不是质数就跳过，如果当前是质数：- 从i的2倍开始向后遍历i的所有倍数，并标记为合数
- 当循环结束时，所有1～n之间的数字都已经标记成了正确的质数或合数
优化：从 p² 开始标记，因为更小的倍数已经被更小的素数筛过了。
基础实现
const int N = 105;
bool isPrime[N] = {0, 0};
// 假设除了0和1，其他都是质数
for (int i = 2; i < N; i++) isPrime[i] = true;
int n;
cin>>n;
// 从2开始，将所有质数的倍数标记成不是质数
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// 从 i*i 开始标记
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}标准实现
vector<bool> sieve(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// 从 i*i 开始标记
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
vector<bool> primes = sieve(n);时间复杂度与空间复杂度
- 时间复杂度：O(n log log n)，非常接近线性
- 空间复杂度：O(n)