标准欧拉筛（线性筛解法）

#include<bits/stdc++.h>
using namespace std;
bool f[100000001];
int p[1000001],cnt=0;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long n,q;
    cin>>n>>q;
    f[1]=1;
    f[0]=1;
    for(int i=2;i<=n;i++){
        if(f[i]==0){
            p[++cnt]=i;
        }
        for(int j=1;p[j]*i<=n&&j<=cnt;j++){
            f[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }
    while(q--){
        int t;
        cin>>t;
        cout<<p[t]<<"\n";
    }
	return 0;
}

当然埃氏筛也可以写，不过线性筛的时间复杂度是O(n)，而埃氏筛的时间复杂度为O(nloglogn)，使用线性筛稍优一些