洛谷P3383 【模板】线性筛素数 欧拉筛板子
#include<bits/stdc++.h> #include<ext/rope> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define ll long long int const int INF = 0x3f3f3f3f; bool prime[100000010]; int num[6000010],cnt=0; void olprime(int n)//欧拉筛法 { mem(prime,1); prime[1]=0; for(int i=2;i<=n;++i) { if(prime[i])//没筛掉 num[++cnt]=i; for(int j=1;j<=cnt&&i*num[j]<=n;++j)//从最小质数2开始寻找最小质因数 { prime[i*num[j]]=0; if(i%num[j]==0)//寻找到最小质因数，为了防止重复筛，break出来 break; } } } int main() { int n,q; scanf("%d%d",&n,&q); olprime(n); for(int i=0;i<q;++i) { int a; scanf("%d",&a); printf("%d\n",num[a]); } return 0; }