题目描述
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)( 一亿)间的所有回文质数。
输入格式
第 1 行: 二个整数 a 和 b .
输出格式
输出一个回文质数的列表，一行一个。
输入输出样例
输入 #1
5 500
输出 #1
5 7 11 101 131 151 181 191 313 353 373 383
#include <stdio.h>
#include <math.h>
int sushu (int n)
{if(n==2) return 1;if(n%2==0) return 0;//2是唯一的偶素数，这样可以减少运行时间for(int i=2;i<=sqrt(n);i++){if(n%i==0) return 0;}return 1;
}
int huiwen (int n)
{//可以采用以下两种方法//采用数组，进行数组元素的比较int a[12];int flag=1;while(n>0){a[flag]=n%10;n/=10;flag++;}for(int i=1;i<=flag/2;i++){if(a[i]!=a[flag-i]) return 0;}return 1;//进行数字反转，绕后将反转数与原数比较/*int sum=0;while(n!=0){sum=sum*10+n%10;n=n/10;}if(sum==n) return 1;else return 0;*/
}
int main ()
{int a,b;scanf("%d %d",&a,&b);for(int i=a;i<=b;i++){if(i==9989900) break;//可以通过打表法把最大的回文素数找出来if(huiwen(i)&&sushu(i))printf("%d\n",i);}
}
这道题主要就是要解决TLE(Time Limit Exceeded）超时的问题。
解决超时可以从以下几点入手：
1、判断素数：2是唯一的偶素数，判断素数时可以只验证奇数即可。
2、判断回文数：可以采用数组或者数字反转的两种方法，都不会超时。
3、打表法求出输出数据的范围，这也是解决本题的关键，通过打表可以发现，回文素数最大便是 9989899，因此让main函数中的循环到9989900便跳出循环即可减少很大一部分的运行时间。