一、题目描述
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)（一亿）间的所有回文质数。
二、思路展开
首先，我们知道要筛选回文数和质数，由于回文数只需判断数字是否左右对称，而质数需要遍历寻找因子，显然找到回文数更加容易。
所以我们先筛选出范围内的回文数，再筛选出其中的质数。
在打代码前，有几点性质需要了解。
2.1 回文数
2.1.1 回文数的性质
- 可以被11整除
- 不存在偶数位的回文数
- 一位数都是回文数
2.1.2 如何检索回文数
在处理回文数之前，学习高精度的写法是必须的。
int p = x; //x为需要存储的数
int pL = 0; //有几位数
while(p>0){
number[pL++] = p%10; //一位一位赋值
p/=10;
}比如我们给x赋值352,那么存到number数组里的效果就是:
number[0]
>>2
number[1]
>>5
number[2]
>>3没错，反向存入~~
接下来对两边的数字进行检查就好啦：
//pL为数位长度
if(pL%2==0){
for(;i<=pL/2-1;i++){ //偶数位
if(number[i]!=number[pL-1-i]){
return 0;
}
}
return 1;
}
for(;i<=(pL-1)/2-1;i++){ //奇数位
if(number[i]!=number[pL-1-i]){
return 0;
}
}
return 1;2.2 质数
2.2.1 质数的性质
- 不能被1和自身以外的数整除
- 2是质数
2.2.2 如何检索质数
由于根号x * 根号x = x，所以可以知道所有因子关于x对称。
举个例子，10 = 2 * 5 = 5 * 2 = sqrt(10)*sqrt(10)。所以前乘数只需要扫到sqrt(x)就可以停了。
这样能节省一半的算法~
由于题目将范围设定在[5,100 000 000]之间，所以我们先过滤掉两位以外的偶数位数(四位数、六位数、八位数)。
原因是这类数可以被11整除，不是质数。因此我们在前期就直接筛去它们。
最后对着每个数直接判断三次就行啦
三、完整代码
#include <bits/stdc++.h>
using namespace std;
int min_(int a,int b){
if(a<b) return a;
else return b;
}
bool checkLen(int x){//检查位数和奇偶
if((x>=1000&&x<=9999)||(x>=100000&&x<=999999)){
return 0;
}
return 1;
}
bool checkMalin(int x){ //检查回文
int number[10];
int p = x;
int pL = 0;
while(p>0){
number[pL++] = p%10;
p/=10;
}
int i=0;
if(pL%2==0){
for(;i<=pL/2-1;i++){ //偶数位
if(number[i]!=number[pL-1-i]){
return 0;
}
}
return 1;
}
for(;i<=(pL-1)/2-1;i++){
if(number[i]!=number[pL-1-i]){
return 0;
}
}
return 1;
}
bool checkPrime(int x){ //检查质数
if(x==2){
return 1;
}
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return 0;
}
}
return 1;
}
int main(){
int min,max;
scanf("%d %d",&min,&max);
if(min%2==0){
min++; //奇数开始
}
max = min_(9999999,max); //回文质数
for(int i=min;i<=max;i+=2){ //奇数
if(!checkLen(i)){
continue;
}
if(!checkMalin(i)){
continue;
}
if(!checkPrime(i)){
continue;
}
printf("%d\n",i);
}
return 0;
}感谢来访与阅读，欢迎各路大佬批评与指点意见
