P1217 [USACO1.5] 回文质数 Prime Palindromes-EW帮帮网

题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)（一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 a 和 b。

输出格式

输出一个回文质数的列表，一行一个。

输入输出样例

输入 #1复制运行

5 500

输出 #1复制运行

说明/提示

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

解题思路：

首先在这个范围里找到所有的回文数，再从回文数中判断它是不是质数就可以了。

找到所有的回文数：

1.首先你要能找到一个位数中的所有回文数，例如2位数，范围10~99中的回文数

思路是：回文数，从前看后于从后看前是一样的，所以可以把这个位数砍成一半，例如12321或123321，砍成123，再123*10+3，再（123*10+3）*10+2等等，变回一个回文数，

根据一个位数找其中的所有回文数的代码为：

vector<long long> number_pali(long long h){//h为一个位数
	vector<long long> array;
	long long start=pow(10,(h-1)/2);
	long long end=pow(10,(h+1)/2)-1;
	long long a,b;
	for(long long i=start;i<=end;i++){
		a=i;
		b=i;
		if(h%2)
			b=b/10;
		while(b){
			a=a*10+b%10;
			b/=10;
		}
		array.push_back(a);
	}
	return array;
}

2.你要能知道这个范围里有多少位数，例如：5~123，有1位数，2位数，3位数;

然后就可以结合1.从一个位数中找到所有的回文数，可以找到这个范围里的所有回文数。

找到一个范围里所有的回文数的代码为：

void pali(long long a,long long b,long long c,long long d){//a,b为这个范围的最小和最大位数，c,d为范围最小数和最大数
	for(long long i=a;i<=b;i++){
		vector<long long> array=number_pali(i);
		for(long long j=0;j<array.size();j++){
			if(isprime(array[j])&&c<=array[j]&&array[j]<=d){
				cout<<array[j]<<endl;
			}
		}
	}
}

判断质数代码为【6k+1优化算法】：

bool isprime(long long h){//6k+1优化算法
	 if(h<=1)
	     return false;
	 if(h<=3)
	     return true;
	if(h%2==0||h%3==0)
		return false;
	for(long long i=5;i<=sqrt(h);i+=6){
		if(h%i==0||h%(i+2)==0){
			return false;
		}
	}
	return true;
}

总体代码为

#include<bits/stdc++.h>
using namespace std;
long long number(long long h){//看这个数有多少位
	long long a=0;
	while(h){
		h/=10;
		a++;
	}
	return a;
}
bool isprime(long long h){//6k+1优化算法
	 if(h<=1)
	     return false;
	 if(h<=3)
	     return true;
	if(h%2==0||h%3==0)
		return false;
	for(long long i=5;i<=sqrt(h);i+=6){
		if(h%i==0||h%(i+2)==0){
			return false;
		}
	}
	return true;
}
vector<long long> number_pali(long long h){//h为一个位数
	vector<long long> array;
	long long start=pow(10,(h-1)/2);
	long long end=pow(10,(h+1)/2)-1;
	long long a,b;
	for(long long i=start;i<=end;i++){
		a=i;
		b=i;
		if(h%2)
			b=b/10;
		while(b){
			a=a*10+b%10;
			b/=10;
		}
		array.push_back(a);
	}
	return array;
}
void pali(long long a,long long b,long long c,long long d){//a,b为这个范围的最小和最大位数，c,d为范围最小数和最大数
	for(long long i=a;i<=b;i++){
		vector<long long> array=number_pali(i);
		for(long long j=0;j<array.size();j++){
			if(isprime(array[j])&&c<=array[j]&&array[j]<=d){
				cout<<array[j]<<endl;
			}
		}
	}
}
int main(){
	long long a,b,number1,number2;
	cin>>a>>b;
	number1=number(a);
	number2=number(b);
	pali(number1,number2,a,b);
	return 0;
}

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