[USACO1.5] 回文质数 Prime Palindromes
题目描述
因为 \(151\) 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 \(151\) 是回文质数。
写一个程序来找出范围 \([a,b] (5 \le a < b \le 100,000,000)\)（一亿）间的所有回文质数。
输入格式
第一行输入两个正整数 \(a\) 和 \(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\) 的回文数：
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;//(处理回文数...)
}
}
}
2.题解
2.1 循环枚举
思路
遍历[a,b]中的所有数，找出其中为回文质数的数，这里注意：没有偶数位的回文质数（除了11）！！！
所以这里我做了三步优化：
1.判断位数（除了11之外，只有奇数位的数才有可能是回文质数）
2.判断素数
3.判断回文数（由于要大量计算，所以放在最后判断）
且素数必然是个奇数（除了2,但是这里范围不包括 5 < a < b <....）,所以只需要遍历[a,b]中的所有偶数即可
if(a % 2 == 0) a++;
for(int i = a; i <= b; i = i + 2){}
代码
#include<bits/stdc++.h>
using namespace std;
// 是否是素数
bool isPrime(int num) {
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
// 是否是回文数
/*字符串方式*/
bool isPalindrome(int num){
string str = to_string(num);
int i = 0, j = str.length() - 1;
while(i <= j){
if(str[i] == str[j]){
i++;
j--;
}
else return false;
}
return true;
}
/*数学方式--翻转检测*/
//bool isPalindrome(int num) {
// int original = num;
// int reversed = 0;
// while (num > 0) {
// reversed = reversed * 10 + num % 10;
// num /= 10;
// }
// return original == reversed;
//}
// 位数判断，有偶数位的回文质数, 除了 11
bool ws(int k) //位数
{
if(k>=10 && k<100 && k!=11 || k>=1000 && k<10000)return false;
if(k>=100000 && k<1000000 || k>=10000000 && k<100000000)return false;
return true;
}
int main(){
int a, b;
cin >> a >> b;
// 素数必然是个奇数，不可能是偶数，除了2（但是这里 5 < a < b <....）
if(a % 2 == 0) a++;
for(int i = a; i <= b; i = i + 2){
if(!ws(i)) continue;
if(!isPalindrome(i)) continue;
if(!isPrime(i)) continue;
printf("%d\n", i);
}
}
2.2 生成回文数
思路
找出所有的回文数再判断它们是不是质数（素数）。
这里我们可以先判断b的位数最大是多少，结合偶数位的数不可能是回文质数，而 b < \(1 * 10^8\)， 所以我们只要考虑位数为 1, 3, 5, 7的几种情况
我们不妨将这几种情况生成回文数的方式都手写出来即可.
这里求b的位数还有一个小技巧：to_string(b).size()， 现将b转换为字符串，再求字符串长度即可得知b的位数
代码
#include<bits/stdc++.h>
using namespace std;
// 判断一个数是否为质数
bool isPrime(long long num) {
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (long long i = 3; i * i <= num; i += 2) {
if (num % i == 0) return false;
}
return true;
}
// 生成位数为 numDigits 的所有回文数
vector<long long> generatePalindromes(int numDigits) {
vector<long long> palindromes;
// 如果是1位数，则只需要考虑[5, 9]的数字
if(numDigits >= 1){
for(int i = 5; i <= 9; i++){
if(isPrime(i)) palindromes.push_back(i);
}
}
if(numDigits >= 2) palindromes.push_back(11);
if(numDigits >= 3){
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
long long palindrome = i * 100 + j * 10 + i;
if(isPrime(palindrome)) palindromes.push_back(palindrome);
}
}
}
if(numDigits >= 5){
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
long long palindrome = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
if(isPrime(palindrome)) palindromes.push_back(palindrome);
}
}
}
}
if(numDigits >= 7){
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
for(int l = 0; l <= 9; l++){
long long palindrome = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
if(isPrime(palindrome)) palindromes.push_back(palindrome);
}
}
}
}
}
return palindromes;
}
int main() {
long long a, b;
cin >> a >> b;
// 在范围 [a, b] 中搜索回文质数
vector<long long> palindromes = generatePalindromes(to_string(b).size()); // 求b的位数，直接转换为字符串，再求长度即可
for (long long palindrome : palindromes) {
if (palindrome >= a && palindrome <= b) {
cout << palindrome << endl;
}
}
return 0;
}
2.3 生成回文数优化
思路
手动生成回文数较为麻烦，如果位数过大，不能一个个手打，这里使用DFS深度优先搜索来递归解决这个问题
代码
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, ans;
//后面用来赋值
bool pri(int x)
{
//判断质数
for (int i = sqrt(x); i >= 2; i--)
if (x % i == 0)
return false;
return true;
}
/*
d：已经生成的位数。
bts：所需的总位数。
s：已经生成的数字组成的字符串。
总体思路: 我只考虑先生成前面的一半（程序后面部分），然后后面的一半在下一次中逆向补充起来（程序前面部分）。
*/
void DFS(int d, int bts, string s)
{
// 已经举出的位数,总位数,已经枚举的数字形成的串
if (d == bts / 2 + (bts % 2) + 1) //检查已经生成的位数是否达到或超过最大的一半（考虑了奇偶性，偶位数要枚举到bts/2位,奇位数要枚举到bts/2+1位）
{
int num = 0;
// 生成正向的一半回文数（包含中间的那个）
for (int i = 0; i < s.length(); i++)
num = num * 10 + (s[i] - '0');
// 如果是偶数位，
if (bts % 2 == 0)
for (int i = s.length() - 1; i >= 0; i--)
num = num * 10 + (s[i] - '0');
// 如果是奇数位
else
for (int i = s.length() - 2; i >= 0; i--)
num = num * 10 + (s[i] - '0');
if (a <= num && num <= b && pri(num))
printf("%d\n", num);
return;
}
// 递归生成下一个数字
for (int i = (d == 1) ? 1 : 0; i <= 9; i++) // 首尾不可以是0，中间的都可以从[0,9]
{
if (d == 1 && i % 2 == 0) //如果当前位是第一位（d == 1），则跳过偶数，因为回文数的第一位不能为0且奇数位上的数字必须为奇数。
continue;
char digit = '0' + i;
DFS(d + 1, bts, s + digit);
}
}
int main()
{
scanf("%d%d", &a, &b);
int x = a, y = b, la = 0, lb = 0;
while (x)
x /= 10, la++;
while (y)
y /= 10, lb++;
for (int i = la; i <= lb; i++)
DFS(1, i, "");
//生成位数在a和b的位数之间的回文数
return 0;
}