回文质数 Prime Palindromes(欧拉筛)

本文主要是介绍回文质数 Prime Palindromes(欧拉筛)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

回文质数 Prime Palindromes

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

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

输入格式
第 1 行: 二个整数 a 和 b .

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

输入输出样例
输入
5 500
输出
5
7
11
101
131
151
181
191
313
353
373
383

PS:383后面是否有空行并不会检测

错误代码

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
#define Max 100000000 
bool IsSu[Max+1];
int Prime[Max];//存放素数的数组
bool IsHWS(int x)
{//思路将个位十百反转，若等于原数，则为回文数int k = x;//储存该数// k = k%10;//求出个位int nums = 0;//存储反转后数while(k!=0){nums = nums*10+k%10;k = k/10;}if(nums==x){return true;}else{return false;}
}int main()
{int a,b;scanf("%d%d",&a,&b);int t = 0;memset(IsSu,true,sizeof(bool)*(Max+1));if(b>=Max){b = Max-1;}//假设标记0为素数//用数组的下标作为素数for(int i=2;i<=b;i++)//遍历寻找素数{if(IsSu[i]==true){//如果是素数Prime[t] = i;t++;//记录素数的个数}for(int j=0;j<t&&i*Prime[j]<=b;j++){IsSu[Prime[j]*i] = false;if(i%Prime[j]==0){break;}}}if(a%2==0){a++;}for(int i=a;i<=b;i++){if(i>10000000) break;if(IsHWS(i)==true&&IsSu[i]==true){printf("%d\n",i);}}return 0;
}

问题分析

一开始根本不会回文数的判断方法，脑子里想的全是栈，然后又不知道什么时候停止入栈，什么时候出栈，结果直接看了大佬的代码，用变量接收x的一个个位上数字，再将个位作为最高位与原x比较
学了回文数判断后，用埃氏筛筛选素数，结果超时，又双看了大佬代码，学了欧拉筛，结果兴奋一试，还是超时，浪费n久后，终于发现：

偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000

偶数位回文数会被11整除
这样只需要给b添加一个条件即可

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
#define Max 100000000 
bool IsSu[Max+1];
int Prime[Max];//存放素数的数组
bool IsHWS(int x)
{//思路将个位十百反转，若等于原数，则为回文数int k = x;//储存该数// k = k%10;//求出个位int nums = 0;//存储反转后数while(k!=0){nums = nums*10+k%10;k = k/10;}if(nums==x){return true;}else{return false;}
}int main()
{int a,b;scanf("%d%d",&a,&b);int t = 0;memset(IsSu,true,sizeof(bool)*(Max+1));if(b>=Max){b = Max-1;}//假设标记0为素数//用数组的下标作为素数for(int i=2;i<=b;i++)//遍历寻找素数{if(IsSu[i]==true){//如果是素数Prime[t] = i;t++;//记录素数的个数}for(int j=0;j<t&&i*Prime[j]<=b;j++){IsSu[Prime[j]*i] = false;if(i%Prime[j]==0){break;}}}if(a%2==0){a++;}if(b>10000000){b=10000000}for(int i=a;i<=b;i++){if(i>10000000) break;if(IsHWS(i)==true&&IsSu[i]==true){printf("%d\n",i);}}return 0;
}