算法题解（可逆素数）

算法题解（可逆素数）

pumpkin_

·

2023-09-30 01:48:23

·

个人记录

算法题解

45 阶段测试 第一题

可逆素数

题目描述：

可逆素数是指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。例如：13是素数，其反序数31也是素数，那么我们就称13和31都是可逆素数。

输入描述：

一行，两个整数m，n，表示待搜索的整数范围。(0

输出描述：

一行，一个整数，表示m~n之间可逆素数的个数。

用例输入1：

1 20

用例输出1：

7

用例输入2：

1000 9999

用例输出2：

204

做题思路：

从两个基本问题入手：

1.如何计算一个数字的可逆数

2.如何判断一个数是否是质数

第一步，封装可逆数字的函数，将一个多位数x的逆序数存储到变量res中去。按照从低位到高位的顺序，依次提取x的每一位数字，并将每次提取的数字从高到低的组成一个新的多位数res

第二步，封装判断是否为质数的函数，注意优化判断区间，如果x是质数则返回true

题解：

/*

题目链接：

https://oj.aicoders.cn/group/139/training/2107/problem/ZJCTD1054

*/

#include

using namespace std;

//求逆序数 123->321

int rev(int x){

int res=0;//res表示逆序数

int num;//存储每一位分离出来的数

while(x){//直到全部分离完为止

num=x%10;//分离出当前x最后一位数字

x=x/10;//下一次分离倒数第二位，要除以10

res=res*10+num;//将分离出来的数字放入逆序数res中

}

return res;

}

//判断质数

bool is_prime(int x){

if (x < 2) return false;//质数一定大于等于2

for (int i = 2; i <= x / i; i ++ )//试除法判断，注意最好缩小范围，遍历到x/i即可

if (x % i == 0)//会被其他自然数整除

return false;

return true;//一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数，才是质数

}

int main(){

int m,n;//m和n表示待搜索的整数范围 的 前端点 和 后端点

cin >> m >> n;//输入

int cnt=0;//存储范围内符合条件的个数，初始为0

for(int i=m;i<=n;i++){//遍历整个范围m~n

int reverse_i=rev(i);//计算当前数字i的可逆数

if(is_prime(i) && is_prime(reverse_i)){//判断，如果i和i的可逆数都是质数

cnt++;//数量+1

}

}

cout << cnt << endl;//输出范围内符合条件的个数

return 0;

}