广州网站服务西安网站制作工作室

求回文素数

题目

素数回文数的个数

题目描述

求 $11$ 到 $n$ 之间（包括 $n$），既是素数又是回文数的整数有多少个。

输入格式

一个大于 $11$ 小于 $10000$ 的整数 $n$。

输出格式

$11$ 到 $n$ 之间的素数回文数个数。

样例 #1

样例输入 #1

23

样例输出 #1

1

提示

回文数指左右对称的数，如：$11$，$12121$。

可以写两个函数判断是否同时符合素数和回文数的要求
素数:

bool is_prime(int a)
{if (a == 1)return true;else{for (int i = 2; i <= sqrt(a); i++)//使用sqrt优化算法, 直接去掉sqrt也行, 记得带上头文件 <cmath>{if (a % i == 0)return false;}return true;}
}

回文数
本题难点主要是回文数的判断
思路: 将数字倒置存储, 比较和原数字是否相同, 相同即为回文.
可以利用中间变量, 每次取到余数(个位), 赋值给一个临时变量reversed
由于要留着原来的数字做比较, 所以不能改变原变量, 需要使用中间变量temp
使用while(temp>0或temp!=0)每次/10(取数字每一位的方法)
最后将倒置的数字和原数字比较

bool huiwen(int a)
{int temp = a,remainder;//由于要留着原来的数字做比较, 所以不能改变原变量, 需要使用中间变量`temp`int reversed = 0;while (temp > 0){remainder = temp % 10;reversed = reversed * 10 + remainder;temp /= 10;}if (reversed == a)//最后将倒置的数字和原数字比较return true;return false;
}

根据本题要求, 写出主程序

int main()
{int n;int cnt = 0;cin >> n;for (int i = 11; i <= n; i++){if (is_prime(i)&&huiwen(i))cnt++;}cout << cnt << endl;
}

完整代码:

#include<iostream>
using namespace std;
#include<cmath>bool is_prime(int a)
{if (a == 1)return true;else{for (int i = 2; i <= sqrt(a); i++){if (a % i == 0)return false;}return true;}
}bool huiwen(int a)
{int temp = a,remainder;int reversed = 0;while (temp > 0){remainder = temp % 10;reversed = reversed * 10 + remainder;temp /= 10;}if (reversed == a)return true;return false;
}int main()
{int n;int cnt = 0;cin >> n;for (int i = 11; i <= n; i++){if (is_prime(i)&&huiwen(i))cnt++;}cout << cnt << endl;
}