洛谷P1217 [USACO1.5] 回文质数 Prime Palindromes

P1217 [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;//(处理回文数...)}}}

#include<bits/stdc++.h>
using namespace std;
int a[50000000];
int isPrime(int num)
{for(int i=2;i<=sqrt(num);i++)if(num%i==0)	return 0;return 1;
}
int makeHuiwen()
{int d1,d2,d3,d4,palindrome,cnt=0;for(d1=1;d1<=9;d1=d1+2)       //1位数{palindrome=d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;} for(d1=1;d1<=9;d1=d1+2)        //2位数 {	palindrome=d1*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;}for(d1=1;d1<=9;d1=d1+2)      //3位数 	  for(d2=0;d2<=9;d2++){palindrome=d1*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;}for(d1=1;d1<=9;d1=d1+2)             //4位数for(d2=0;d2<=9;d2++){palindrome=d1*1000+d2*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;	}for(d1=1;d1<=9;d1=d1+2)					//5位数 	for(d2=0;d2<=9;d2++)		for(d3=0;d3<=9;d3++){palindrome=d1*10000+d2*1000+d3*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;	}for(d1=1;d1<=9;d1=d1+2)					//6位数 	for(d2=0;d2<=9;d2++)		for(d3=0;d3<=9;d3++){palindrome=d1*100000+d2*10000+d3*1000+d3*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;	}for(d1=1;d1<=9;d1=d1+2)	                //7位数 for(d2=0;d2<=9;d2++)for(d3=0;d3<=9;d3++)for(d4=0;d4<=9;d4++){palindrome=d1*1000000+d2*100000+d3*10000+d4*1000+d3*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;}for(d1=1;d1<=9;d1=d1+2)	                //8位数 for(d2=0;d2<=9;d2++)for(d3=0;d3<=9;d3++)for(d4=0;d4<=9;d4++){palindrome=d1*10000000+d2*1000000+d3*100000+d4*10000+d4*1000+d3*100+d2*10+d1;if(isPrime(palindrome)) cnt++,a[cnt]=palindrome;}return 0;
}int main()
{int small,big;cin>>small>>big;makeHuiwen();for(int i=0;i<=50000000;i++){if(a[i]>=small && a[i]<=big){cout<<a[i]<<endl;}}return 0;}