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

额这道题其实并不难
先上题目:

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

写一个程序来找出范围 [ a , b ] ( 5 ≤ a < b ≤ 100 , 000 , 000 ) [a,b] (5 le a < b le 100,000,000) [a,b](5≤a 输入格式

第 1 行: 二个整数 a 和 b .

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

5 500

5
7
11
101
131
151
181
191
313
353
373
383

代码如下:

#include 
#include 
using namespace std;
bool SUSHU(int a){
	if(a==1){
		return false;
	}
	if(a%6!=1&&a%6!=5){
		return false;
	}
	int i=a;
	while (i>0){
		i/=10;
	}
	if(i==2||i==4||i==5||i==6||i==8){
 	    return false;
	}
	int tmp = sqrt(a);
    for(i = 5; i <= tmp; i+=6) {
  		if(a % i == 0 || a%(i+2)==0) return false;
   	}
    return true;
}
bool hui(int a){
	if(a==0){
		return false;
	}
	int j=0,i=a;
	for (i=a;i>0;i/=10){
		j=j*10+i%10;
	}
	return a==j; 
}
int main(int argc, char** argv) {
	int i,j,q=0;
	int v[500000] = {0};
    cin>>i>>j;
    if(i>10000000){
    	i=10000000;
	}
	if(j>10000000){
		j=10000000;
	}
	for (int n=i;n<=j;n++){
		if(hui(n)){
   	        v[q]=n;q++;
		}
	}
	for (int n=0;n<=q;n++){
		if(SUSHU(v[n])){
            cout< 
暴力枚举出奇迹
 首先1~3行:老样子
 4~23行:判断素数(升级版)
 24~33行:判断回文数
 接下来先筛选出所有的回文数(更快)
 再筛选出素数
 PS:此题与Vijos捕风捉影大同小异:
 
 
描述
有一天，雄霸传授本人风神腿法第一式：捕风捉影..............的步法（弟子一：
堂主，你大喘气呀。风：你给我闭嘴。）捕风捉影的关键是换气（换不好就会大喘
气...）。

使用捕风捉影这一招时并不是每一步都喘气，而是在特定的步数喘气。一般来说功力
越高，喘气越稀疏。喘气的步数符合特定规律：第一要是SUSHU（弟子二：哇塞！堂
主，你还会鸟语，我好好崇拜你呦！可是SUSHU是什么意思呢？风：笨蛋，那是汉语
拼音！）第二要是一个回文数，回文数就是正反念一样的数，如：123321，121，
5211314（弟子三：堂主，最后一个好象不是...风：废话，当然不是了，我是考察一
下你们的纠错能力！）现在给出两个数M，N(5<=M 
格式
输入格式
两个整数M，N。用空格隔开。

输出格式
在M，N之间的换气点，每个一行。
 
样例1
 样例输入1
 
100 500
 
样例输出1
 
101
131
151
181
191
313
353
373
383