题目
题目描述
因为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
想法
一看到那个a、b的范围，可能就觉得暴力，可能会超时，但是我还是抱着试一试的想法用了暴力。
数学知识：
- 除2之外的素数都是奇数
上过小学的人都知道。那我就来证明一下第二个结论。 - 偶数位回文数能够被11整除
（为什么我上传的图片是歪的）
- [a,b]范围最大是[5,100000000]
所以：
一位数：5，7
两位数：11
四位、六位、八位都不存在回文数素数
九位只有一个数，且为偶数。
下面是解决这个问题的两种方法代码：
- 直接从a，遍历到b，判断是否是回文数素数。
- 构造回文数，再判断是否为素数。
第一种
该方法直接从a开始遍历到b，由于除2以外所有的质数都是奇数，所以循环增量为2。
#include<stdio.h>
#include<math.h>
using namespace std;
//判断该数是否为回文数
bool check_h(int x){
int y=x;
int num=0;
while(y!=0){
num = num*10+y%10;
y/=10;
}
if(num==x){
return true;
}else{
return false;
}
}
//判断该数是否为素数(采用6素数法)
bool check_s(int p){
if(p%6 != 1 && p%6 != 5)return false;
int q = sqrt(p);
for(int i=5;i<=q;i+=6){
if(p%i == 0 || p%(i+2) == 0)return false;
}
return true;
}
//根据：偶数位回文数能够被11整除。(除11)
//判断是否属于偶数位回文数。
bool check_w(int x){
//二位、四位
if(x>=10&&x<100&&x!=11 || x>=1000&&x<=10000){
return false;
}
//六位、八位
if(x>=100000 && x<=1000000 || x>=10000000&&x<=100000000){
return false;
}
return true;
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
//因为下面的循环增量为2.所以若a为偶数，需要+1
if(a%2 == 0){a+=1;}
for(int i=a;i<=b;i+=2){
if(!check_w(i))continue;
if(check_h(i)){
if(check_s(i))printf("%d\n",i);
}
}
}
第二种
#include<stdio.h>
#include<math.h>
using namespace std;
//求一个数字的位数
int check_w(int x){
int sum=0;
int y=x;
while(y!=0){
sum++;
y/=10;
}
return sum;
}
//判断一个数是否为素数(采用6素数法)
bool check_s(int x){
if(x%6 != 1 && x%6!=5){
return false;
}
int q = sqrt(x);
for(int i=5;i<=q;i+=6){
if(x%i == 0 ||x%(i+2)==0)return false;
}
return true;
}
int main(){
int a,b;//题目输入的两个值
int p;
int d1,d2,d3,d4;//循环变量
scanf("%d%d",&a,&b);
int m = check_w(a);//计算a的位数
int n = check_w(b);//计算b的位数
//当a<10时，判断[a,b]的范围里是否包括5,7，包括就输出。
if(m<=1){
if(a<=5){printf("5\n");}
if(a<=7){printf("7\n");}
}
//判断是否包含11
if(m<=2&&n>=2){
if(a<=11&&b>=11){
printf("11\n");
}
}
//三位数
if(m<=3&&n>=3){
for (d1 = 1; d1 <= 9; d1+=2) {
for (d2 = 0; d2 <= 9; d2++) {
p = 100*d1 + 10*d2 + d1;
//生成回文数
if(p>=a){
if(p<=b){
if(check_s(p))printf("%d\n",p);
}else{
return 0;
}
}
}
}
}
//五位数
if(m<=5&&n>=5){
for(d1 = 1;d1<=9;d1+=2){
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
p = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;
//生成五位回文数
if(p>=a){
if(p<=b){
if(check_s(p))printf("%d\n",p);
}else{
return 0;
}
}
}
}
}
}
//七位数
if(m<=7&&n>=7){
for(d1 = 1;d1<=9;d1+=2){
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
for(d4 = 0;d4<=9;d4++){
p = 1000000*d1+100000*d2 + 10000*d3 +1000*d4 + 100*d3 + 10*d2 + d1;
//生成七位回文数
if(p>=a){
if(p<=b){
if(check_s(p))printf("%d\n",p);
}else{
return 0;
}
}
}
}
}
}
}
}
完
有什么疑问，可以在下面留言。
若有错误，请您及时指出。
个人博客：陪你一起终身学习！|岳金钊&个人博客