欧拉筛

entelecheia_with_3 · 2023-12-17 19:41:12 · 算法·理论

欧拉筛法的核心：

1.素数的倍数是合数。
2.让每一个合数都只被它最小的质因数标记。(详见12~16行）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e8+10,N=1e6+10;
int n,q,k;
bool vis[maxn];
int prime[N],idx;
void solve(){
    for(int i=2;i<=n;i++){
        if(!vis[i]){//说明是素数 
            prime[++idx]=i; 
        }
        for(int j=1;j<=idx;j++){
            if(prime[j]*i>n)break;
            vis[prime[j]*i]=1;
            if(!(i%prime[j]))break;//说明后面的数的最小质因子将不再是prime[j] 
        }
    }
}
void ans(){
    for(int i=1;i<=q;i++){
        cin>>k;
        cout<<prime[k]<<endl;       
    } 
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    solve();
    ans(); 
    return 0;
} 

时间复杂度 O(n)