埃氏筛法简介

​【埃氏筛法简介】
● 埃氏筛，全称埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种用于找出自然数范围内所有素数的经典算法，由古希腊数学家埃拉托斯特尼提出。其核心思想是：从最小的素数 2 开始，逐步筛除每个素数的所有倍数，最终剩下的未被筛除的数即为素数。埃氏筛的核心代码如下所示。

st[0]=st[1]=false;
for(int i=2; i*i<=n; i++) {if(!st[i]) continue;for(int j=2*i; j<=n; j+=i) st[j]=false;
}

该算法的时间复杂度为 O(n log log n)，在处理 10^6 及以内的素数查找时效率极高，是数论和算法竞赛中最常用的素数查找方法。 

● 埃氏筛法的核心局限性是重复筛除合数。

上图中的不同颜色，代表不同批次筛掉的合数。叠加有椭圆的数，代表进行了重复筛除。
实际开发中，可将核心代码中 j 的开始位置从 2*i 优化为 i*i 。优化后的核心代码如下所示。

st[0]=st[1]=false;
for(int i=2; i*i<=n; i++) {if(!st[i]) continue;for(int j=i*i; j<=n; j+=i) st[j]=false;
}

由下图易见，j 的开始位置从 2*i 优化为 i*i 优化后，重复筛除的次数明显减少。

● 欧拉筛（线性筛） 通过每个合数仅被其最小质因数筛除的规则，将时间复杂度优化至严格 O (n)，使得欧拉筛是处理更大范围素数（如 1e7~1e8）的优选算法。欧拉筛（线性筛）没有埃氏筛法重复筛除合数的核心局限性，

【埃氏筛法代码】
代码来源于“洛谷 P3383”：https://blog.csdn.net/hnjzsyjyj/article/details/157643126

#include<bits/stdc++.h>
using namespace std;vector<bool> st; //isPrime
vector<int> p; //primevoid e_sieve(int n) { //eratosthenes_sievest.assign(n+1,true); //0~nst[0]=st[1]=false;for(int i=2; i*i<=n; i++) {if(!st[i]) continue;for(int j=i*i; j<=n; j+=i) st[j]=false;}for(int i=2; i<=n; i++) {if(st[i]) p.push_back(i);}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,q,k;cin>>n>>q;e_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
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/157643126
https://blog.csdn.net/hnjzsyjyj/article/details/157615246
https://blog.csdn.net/hnjzsyjyj/article/details/155538927

​