首页 > 代码库 > HDU 1431

HDU 1431

可以先找出回文数,再用素数测试来判是否为素数即可。

打回文数时,因为左右对称,可以只枚举后半部,然后通过逆转得到前半部分。

#include <iostream>#include <cstdio>#include <time.h>#include <stdlib.h>#include <algorithm>using namespace std;const int Max=200000;int huiwen[Max],answer[Max];int htop;int anter(int i){	int ans=1;	while(i){		ans*=10;		i--;	}	return ans;}int gethuiwen(int t,int p){	int ans=0;	while(p>1){		ans*=10;		ans+=(t%10);		p/=10;		t/=10;	}	return ans;}void for_back(){	htop=0;	for(int i=5;i<=9;i++)	huiwen[htop++]=i;	for(int i=2;i<=8;i++){		int p=anter(i/2);	//	cout<<p<<endl;		if(i%2){			for(int k=0;k<=9;k++){				for(int t=0;t<p;t++){					if(t%10==0) continue;					int tail=gethuiwen(t,p);				//	cout<<tail<<‘ ‘<<t<<endl;					huiwen[htop++]=(tail*10+k)*p+t;				}			}		}		else{				for(int t=0;t<p;t++){					if(t%10==0) continue;					int tail=gethuiwen(t,p);					huiwen[htop++]=(tail)*p+t;				}		}	}//	cout<<huiwen[htop-1]<<endl;//	for(int i=10;i<=50;i++)//	cout<<huiwen[i]<<endl;}long long random(long long  n){	return (long long )((double)rand()/RAND_MAX*n+0.5);}long long quick(long long a,long long k,long long m){	long long ans=1;	while(k){		if(k&1){			ans=ans*a%m;		}		k>>=1;		a=a*a%m;	}	return ans;}bool Miller_Rabin(long long k){	for(int i=1;i<=50;i++){		long long  a=random(k-2)+1;		if(quick(a,k-1,k)!=1)		return false;	}	return true;}int main(){	srand(time(0));	for_back();	int tmp=htop; htop=0;//	cout<<huiwen[tmp-1]<<endl;	for(int i=0;i<tmp;i++){	//	cout<<"NO"<<endl;		if(Miller_Rabin(huiwen[i])){		//	cout<<"YES"<<endl;		//	break;		huiwen[htop++]=huiwen[i];		}	}	int a,b,ast;	while(scanf("%d%d",&a,&b)!=EOF){		ast=0;		for(int i=0;i<htop;i++){			if(huiwen[i]>=a&&huiwen[i]<=b)			answer[ast++]=huiwen[i];		}		sort(answer,answer+ast);		for(int i=0;i<ast;i++)		printf("%d\n",answer[i]);		cout<<endl;	}	return 0;}

  

HDU 1431