【欧拉筛法简介】
● 欧拉筛（Euler Sieve / Linear Sieve）是一种线性时间复杂度（O(n)）的素数筛选算法，核心目标是找出 2~n 范围内的所有素数，且保证每个合数只被它的最小质因子筛除一次 —— 这是它区别于其他筛法（如埃氏筛）的关键，也是 “线性复杂度” 的来源。
● 欧拉筛（线性筛） 通过每个合数仅被其最小质因数筛除的规则，将时间复杂度优化至严格 O(n)，使得欧拉筛是处理更大范围素数（如 1e7~1e8）的优选算法。欧拉筛（线性筛）没有埃氏筛法重复筛除合数的核心局限性。埃氏筛的核心代码如下所示。
void euler_sieve(int n) {st.assign(n+1,true); //0~nst[0]=st[1]=false;for(int i=2; i<=n; i++) {if(st[i]) p.push_back(i);for(int j=0; (LL)p[j]*i<=n; j++) {st[p[j]*i]=false;if(i%p[j]==0) break;}}
}
● 但是要注意，欧拉筛不是欧拉发明的。之所以叫欧拉筛，原因在于欧拉筛的核心思想用到了整数唯一分解定理（任何一个大于 1 的整数 N，都可以唯一地表示成若干个质数的乘积）。而欧拉对此贡献巨大，所以后人把这种线性筛尊称为：欧拉筛（Euler sieve）。
● 示意图中用颜色“赤橙黄绿青蓝紫”表示被欧拉筛（线性筛）依次筛掉的数。显然，没有被重复筛除的合数。
● 欧拉筛（线性筛） 为什么 i%p[j]==0 时要 break？
☆ 两个前提
（1）欧拉筛的核心原则：每个合数只会被它的最小质因子筛掉（这是线性复杂度的关键）。 （2）p[j] 是按从小到大顺序存储的素数（p[0]=2, p[1]=3, p[2]=5...）。
☆ 核心逻辑
（1）当 i % p[j] == 0 时，说明 p[j] 是 i 的最小质因子（因为 p[j] 是从小到大遍历的，第一个能整除 i 的素数就是最小质因子）。此时 i = p[j] * m（m 是一个整数）。接下来我们看下一个要筛的数是 p[j+1] * i，代入 i = p[j] * m 可得：p[j+1] * i = p[j+1] * p[j] * m = p[j] * (p[j+1] * m)。
（2）这里能明显看出，这个数 p[j+1] * i 的最小质因子是 p [j]（因为 p[j] < p[j+1]），而不是 p[j+1]。所以这个数 p[j+1] * i 不应该在当前轮次（用 p [j+1] 筛）被标记，而应该在后续某个 i' = p[j+1] * m 时，被 p[j] 筛掉（因为 p[j] 是它的最小质因子）。
【欧拉筛法代码】
代码来源于“洛谷 P3383”：
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
vector<bool> st; //isPrime
vector<int> p; //primevoid euler_sieve(int n) {st.assign(n+1,true); //0~nst[0]=st[1]=false;for(int i=2; i<=n; i++) {if(st[i]) p.push_back(i);for(int j=0; (LL)p[j]*i<=n; j++) {st[p[j]*i]=false;if(i%p[j]==0) break;}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,q,k;cin>>n>>q;euler_sieve(n);while(q--) {cin>>k;cout<<p[k-1]<<"\n";}return 0;
}/*
in:
100 5
1
2
3
4
5out:
2
3
5
7
11
*/
【参考文献】