[USACO1.5] 回文质数 Prime Palindromes
题目链接(洛谷)
题目描述
因为 151 151 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 151 151 是回文质数。
写一个程序来找出范围
[
a
,
b
]
(
5
≤
a <
b
≤
100
,
000
,
000
)
[a,b] (5 \le a < b \le 100,000,000)
[a,b](5≤a 输入格式
第一行输入两个正整数 a a a 和 b b b。
输出格式
输出一个回文质数的列表,一行一个。
样例 #1
样例输入 #1
5 500
样例输出 #1
5 7 11 101 131 151 181 191 313 353 373 383
提示
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文数再判断它们是不是质数(素数).
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数,你可能需要几个像下面这样的循环。
题目翻译来自NOCOW。
USACO Training Section 1.5
产生长度为 5 5 5 的回文数:
for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数 for (d2 = 0; d2 <= 9; d2++) { for (d3 = 0; d3 <= 9; d3++) { palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...) } } }
题意
题目要求找出范围 [ a , b ] [a,b] [a,b]( 5 ≤ a < b ≤ 100 , 000 , 000 5 \le a < b \le 100,000,000 5≤a
思路
- 首先,定义了两个辅助函数 CheckHw 和 CheckSs 分别用于检查一个数是否是回文数和是否是素数。
- 然后,通过输入的范围 [ a , b ] [a,b] [a,b] 遍历所有奇数(因为只有>2的奇数才可能是素数)。
- 对于每一个奇数,使用 CheckHw 判断是否是回文数,然后再使用 CheckSs 判断是否是素数。
- 如果同时满足回文数和素数的条件,输出该数。
坑点
- 注意输入范围,确保
a
a
a 和
b
b
b 满足
5
≤
a <
b
≤
100
,
000
,
000
5 \le a < b \le 100,000,000
5≤a
- 注意循环条件和步长的选择,例如 for (long long int i = a; i <= b; i += 2) 表示从 a a a 开始,每次增加 2 2 2。
- 注意 sqrt(num) 的使用,确保对于大范围的数值,不会出现精度问题。
代码
#include#include using namespace std; // 检查回文数 bool CheckHw(int num) { int reversed = 0; int temp = num; for(; num ; num /= 10) { reversed = reversed * 10 + num % 10 ; } return reversed == temp; } // 检查素数 bool CheckSs(int num) { if (num < 2) return false; for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) return false; } return true; } int main() { long long int a, b; cin >> a >> b; // 如果 a 是偶数,向上取到下一个奇数 if (a % 2 == 0) a++; for (long long int i = a; i <= b; i += 2) { if (CheckHw(i) && CheckSs(i)) { cout << i << "\n"; } } return 0; }