C++ 中的 **普通筛、埃氏筛、线性筛**，它们都是求质数或判断质数的方法

普通筛、埃氏筛、线性筛，它们都是求质数或判断质数的方法，但原理和复杂度不同。

1️⃣ 普通筛（暴力判断质数）

思路：

• 对每个数 i（2 ≤ i ≤ n），判断它是否能被小于它的数整除。
• 如果不能整除，则 i 是质数。

复杂度：

• 最坏情况下 O(n√n)，当 n 较大时效率低。

C++ 示例：

#include <bits/stdc++.h>
using namespace std;bool isPrime(int x) {if (x < 2) return false;for (int i = 2; i * i <= x; ++i)if (x % i == 0) return false;return true;
}int main() {int n;cin >> n;for (int i = 2; i <= n; ++i) {if (isPrime(i)) cout << i << " ";}return 0;
}

---

2️⃣ 埃氏筛（Sieve of Eratosthenes）

思路：

1. 建立长度为 n 的布尔数组 is_prime，初始都为 true。
2. 从 2 开始，若 i 是质数，则把 i 的所有倍数标记为非质数。
3. 最终 is_prime[i] 为 true 的就是质数。

复杂度：

• O(n log log n)
• 对 n ≤ 10⁷ 或 10⁸ 都够用。

C++ 示例：

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<bool> is_prime(n+1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i*i <= n; ++i) {if (is_prime[i]) {for (int j = i*i; j <= n; j += i)is_prime[j] = false;}}for (int i = 2; i <= n; ++i) {if (is_prime[i]) cout << i << " ";}return 0;
}

---

3️⃣ 线性筛（Linear Sieve / 欧拉筛）

特点：

• 保证每个合数只被它最小的质因子标记一次。
• 可以顺序生成质数数组 primes。
• 复杂度 O(n)（比埃氏筛更快）。

思路：

1. 遍历每个数 i（2 ≤ i ≤ n）

2. 如果 i 是质数，加入 primes 数组

3. 遍历 primes 数组：

   • 计算 i * primes[j] ≤ n
   • 标记 i * primes[j] 为非质数
   • 如果 i % primes[j] == 0，则 break（保证每个数只被它最小的质因子标记一次）

C++ 示例：

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> primes;vector<bool> is_prime(n+1, true);for (int i = 2; i <= n; ++i) {if (is_prime[i]) primes.push_back(i);for (int p : primes) {if (i * p > n) break;is_prime[i*p] = false;if (i % p == 0) break;}}for (int p : primes) cout << p << " ";return 0;
}

特点对比：

筛法	时间复杂度	优点	缺点
普通筛	O(n√n)	代码简单	n 大时慢
埃氏筛	O(n log log n)	高效，易实现	不能直接获取最小质因子
线性筛	O(n)	高效，可求最小质因子	实现稍复杂

---