TIOJ 1535 嘿!! Let's Go E-m-i-r-p!!

poao899    14360K    3858MS    G++     0.93K     2009-11-11 14:05:58                                     .




很奇怪

之前TLE得超無辜

結果寫完USACO 1.5 sprime莫名其妙就過了...






//**************************

//emirp

#include<stdio.h>
#include<math.h>
#define MAX 11293974
bool notPrime[MAX];
int prime[744648],pCnt;
int emirp[100000],eCnt,sqMax;
bool testPrime(int k){
	int sqk=(int)sqrt(k);
	for(int i=0;i<pCnt&&prime[i]<=sqk;i++)
		if(k%prime[i]==0)
			return 0;
	return 1;
}
inline bool isPrime(int k){
	if(k%2==0)return 0;
	if(k<MAX)return !notPrime[k];
	else return testPrime(k);
}
int t,n;
main(){
	sqMax=(int)(sqrt(MAX));
	int i;
	for(i=3;i<=sqMax;i+=2)
		if(!notPrime[i]){
			prime[pCnt++]=i;
			for(int j=i*i;j<=MAX;j+=i)
				notPrime[j]=1;
			}
	for(;i<MAX;i+=2)
		if(!notPrime[i])
			prime[pCnt++]=i;
	for(int j=0;j<pCnt;j++){
		int k=0,p=prime[j];
		if(p<10)continue;
		while(p>0){
			k=k*10+p%10;
			p/=10;
		}
		if(k==prime[j])continue;
		if(isPrime(k))
			emirp[eCnt++]=prime[j];
	}
	//printf("%d %d\n",pCnt,eCnt);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%d\n",emirp[n-1]);
	}
}