数论进阶刷题柱

洛谷P3383 线性筛素数

线性筛，那很模板了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;//1e9+7;
ll read(){ll x;scanf("%lld",&x);return x;}
ll quick(ll a,ll b,ll mod){ll t=1;while(b){if(b&1)t=t*a%mod;b=b/2;a=a*a%mod;}return t;}
int lowbit(int x){return x&(-x);}
int pri[6000000],v[100000010],cnt;
void work()
{cout<<pri[read()]<<'\n';
}
int main()
{// freopen("queue.in","r",stdin);// freopen("queue.out","w",stdout);int n=read();for(int i=2;i<=n;i++){if(v[i]==0){pri[++cnt]=i;v[i]=i;}for(int j=1;1ll*i*pri[j]<=n&&j<=cnt&&pri[j]<=v[i];j++)v[i*pri[j]]=i;}for(int t=read();t;t--)work();
}