代码如下：

#include<cstdio>
#include<stdlib.h>
#include<ctime>
#define maxnyxzs 1772753356
#define maxn 1772753356
using namespace std;
bool iff;
long long gn(){/*get number*/
	char ch=getchar();
	long long fh=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')fh=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return (fh==1)?x:-x;
}
long long n;
long long a[maxnyxzs]={0,2},aa[maxnyxzs];
long long cfs=2/*乘法式的值*/,nc=3/*next_chengfashi 乘法式的下一个质数*/,nci=2/*next_chengfashi_i 乘法式的下一个质数的坐标*/;
long long top=2,dl=1/*duilie_long,队列长度*/ ;
long long tmp;
long long hs[maxn],w,m;
long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long pdss(long long a,long long b,long long mod){
    	if(b==1) return a%mod;
        if(b&1) return ((a%mod)*pdss(a,b-1,mod))%mod;
        long long t=pdss(a,b>>1,mod);
        long long tt=(t*t)%mod;
        if (tt==1)// 二次探测
           if(t!=1 && t!=mod-1) iff=false;
       return tt;
 }
bool pd(long long p){
    int T=30;
    iff=true;
    while (T--){
        long long a=rand()%10000*rand()+1; //不能取0
        while (gcd(a,p)!=1){ if (a<p || a%p!=0) return false;a=rand()%1000*rand()+1;}
        if (pdss(a,p-1,p)!=1|| !iff) return false;
    }
    return true; 
}
void shuru(){
	n=1772753356;
}
void clac(){
	while(1){
		////<<"step1"<<endl;
		while(1){
			if(a[top]==-1){
				top--; 
				continue;
			}
			if(top<nci)break;
			tmp=cfs-a[top];
			if(tmp>n)return;
			////<<"--------"<<endl;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
				////("%lld\n",tmp);
				////<<"top:"<<top<<endl;
				////<<"a[top]:"<<a[top]<<endl;
			}
			top--; 
		}
	
		////<<"step2"<<endl;
		tmp=cfs-1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
			////("%lld\n",tmp);
			////<<"top:"<<top<<endl;
			////<<"a[top]:"<<a[top]<<endl;
		}
		////<<"step3"<<endl;
		tmp=cfs+1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
			////("%lld\n",tmp);
			////<<"top:"<<top<<endl;
			////<<"a[top]:"<<a[top]<<endl;
		}
		////<<"step4"<<endl;
		top=nci;
		while(1){
			if(a[top]==-1){
				top++;
				continue;
			}
			tmp=cfs+a[top];
			if(tmp>n)return;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
				////("%lld\n",tmp);
				////<<"top:"<<top<<endl;
				////<<"a[top]:"<<a[top]<<endl;
			}
			if(tmp>cfs*a[nci]-a[dl]){
				cfs*=a[nci];
				for(int i=nci+1;i<=dl;i++){
					if(a[i]%a[nci]==0){
						a[i]=-1;
					}
				} 
				for(int i=nci;a[i]==-1;++i,++nci);
				nci++;
				top=dl; 
				goto step1;
			}
			top++;
		}
		step1:
		////<<"dl:::::"<<dl<<endl;
		top=dl; 
	}
}
long long nn;
void shuchu(){
	top=1;
	for(int i=1;i<=dl;++i){
		if(a[i]!=-1){
			if(pd(a[i])){
				aa[top++]=a[i];
			}
		}
	}
	nn=gn();
	for(int i=1;i<=nn;++i){
		printf("%lld",aa[gn()]);
	}
	////<<endl<<"-----------------"<<endl;

}
int main(){
	srand((unsigned)time(NULL));
	shuru();
	clac();
	////("clac over\n");
	shuchu();
	return 0;
}//数组aa中存储的是n以下的质数

算法核心思路： 运用质数判定定理，实现O（1）的判定队列中是质数还是合数。

时间复杂度： shuru() o(1)

clac() o(m+w)

shuchu() o(m+w)

故为o(m+w)(m是n以下的质数个数，w是质数以下的非正常合数个数）

空间复杂度：o（m+w）