本文共 1545 字,大约阅读时间需要 5 分钟。
一个性质:偶数位的回文数都是11的倍数(11本身除外),所以偶数位的不用考虑,接下来我们就构造奇数位的回文数,然后判断这个数是不是素数就行了。
代码如下:
/*ID: 15674811LANG: C++TASK: pprime*/#include#include #include #include #include using namespace std;bool is_prime(int n){ int k=sqrt(n)+0.5; for(int i=2;i<=k;i++) if(n%i==0) return 0; return 1;}///构造得到10000000以内的奇数位回文数int Get(int *b){ int cnt=0; ///1位的回文数 for(int i=1;i<=9;i++) b[cnt++]=i; b[cnt++]=11; ///偶数位的回文数都是11的倍数,所以不用考虑 ///3位的回文数 for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) { int d=i*100+j*10+i; b[cnt++]=d; } ///5位的回文数 for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) { int d=10000*i+1000*j+100*k+10*j+i; b[cnt++]=d; } ///7位的回文数 for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) for(int d=0;d<=9;d++) { int d1=1000000*i+100000*j+10000*k+1000*d+100*k+10*j+i; b[cnt++]=d1; } return cnt;}int main(){ int b1[20000]; ofstream cout("pprime.out"); ifstream cin("pprime.in"); int cnt=Get(b1); int a,b; while(cin>>a>>b) { for(int i=0;i =a&&b1[i]<=b&&is_prime(b1[i])) cout< < b) break; } return 0;}
转载地址:http://xkrfb.baihongyu.com/