1.什么是埃氏筛
质数的倍数，绝对不是质数（比如 2 是质数，那 4、6、8 肯定都是合数）。
2. 举个栗子（找 1 到 20 的质数）
- 先把 1 到 20 排成一排。（1 不是质数先踢掉）。
- 遇到 2：2 还在队伍里，说明它是质数！接着把队伍里 2 的倍数（4, 6, 8, 10…）全踢出去。
- 遇到 3：3 还在队伍里，它是质数！把 3 的倍数（6, 9, 12…）全踢出去。
- 遇到 4：咦？4 刚才已经被 2 踢出去了，说明 4 是合数，直接跳过。
- 遇到 5：5 还在，它是质数！把 5 的倍数（10, 15, 20）踢出去。
- 一直这样扫到最后，剩下的
2, 3, 5, 7, 11, 13, 17, 19就是所有质数。
3.如何用代码实现
定义 st 数组，st [i] 表示 i 是否为素数。prime 数组用于存储所有素数，cnt 表示当前素数的数量。
从 2 开始遍历到 n，若 st [i] 为 false，则将 i 加入 prime 数组，同时将 i 的所有倍数标记为 true。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int primes[N],st[N];//st[i]=false代表不是素数
int n,cnt;
int main(){
cin>>n;
for(int i=2;i<=n;i++){
if(st[i]==0){
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i) st[j]=1;
}
}
cout<<cnt<<endl;
return 0;
}其中的j=i+i换成j=i*i可以优化时间复杂度，可以用放缩来解释，但是需要特判。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int prime[N],cnt=0;
bool st[N];//st[i]=false 表示是素数
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
if(st[i]) continue;
prime[++cnt]=i;
if((long long)(i)*i>n) continue;
for(int j=i*i;j<=n;j=j+i){
st[j]=true;
}
}
cout<<cnt;
return 0;
}4.模板
模板一：标准埃氏筛
这是最经典的用法，用于快速找出所有小于等于 N的质数，并判断某个数是否为质数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // 根据题目要求修改最大范围
vector<int> primes; // 存储筛选出的所有质数
vector<bool> is_prime; // is_prime[i] 表示 i 是否为质数
// 初始化标准埃氏筛
void init_sieve(int n) {
is_prime.assign(n + 1, true);
is_prime[0] = is_prime[1] = false; // 0 和 1 不是质数
// 优化1：外层循环只需遍历到 sqrt(n) 即可
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
// 优化2：内层循环直接从 i * i 开始标记，因为 i * 2, i * 3 等已经被之前的质数 2, 3 标记过了
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
// 收集所有质数
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
}
}
}
int main() {
init_sieve(100); // 找出 100 以内的质数
cout << "25 is prime? " << is_prime[25] << "\n"; // 输出 0 (false)
return 0;
}时间复杂度：o(nloglogn)
模板二：质因子预处理筛
如果你遇到的题目不光要判断质数，还需要频繁获取每个数字包含哪些质因子
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
// prime_factors[i] 存储数字 i 的所有不同质因子
vector<vector<int>> prime_factors(MAXN);
// 利用 Lambda 表达式在 main 函数之前完成全局预处理 (常数极小，力扣/打比赛常用)
int init = []() {
for (int i = 2; i < MAXN; i++) {
// 如果 prime_factors[i] 是空的，说明它没有被前面的数整除过，它本身就是质数
if (prime_factors[i].empty()) {
// 将这个质数 i 塞给它所有的倍数
for (int j = i; j < MAXN; j += i) {
prime_factors[j].push_back(i);
}
}
}
return 0;
}();
int main() {
// 因为预处理在全局域已经跑完了，这里可以直接查表
cout << "Prime factors of 12: ";
for (int p : prime_factors[12]) {
cout << p << " "; // 输出 2 3
}
cout << "\n";
return 0;
}时间复杂度：o(nlogn)
