题解报告：hdu 1431 素数回文

Problem Description

xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);

Input

这里有许多组数据，每组包括两组数据a跟b。

Output

对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。

Sample Input

5 500

Sample Output

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

解题思路：这道题交了10次才A掉（怪菜鸡太弱。。。），刚开始是直接用欧拉筛模板+简单的回文判断，结果显示超内存。。。欧拉筛的时间复杂度可是O（n）线性时间。。。重新读题，其最大范围是10^8，但多次小修改提交后还是超内存。于是直接改用暴力，结果显示超时，无奈将这两个算法结合在一起，结果还是显示超时。当看到题解之后才明白，欧拉筛（埃氏筛也一样）里面用到int数组开辟的空间比较占内存，这就是超内存的原因，而单独用bool类型来判断的话就刚刚好，因为它占1个字节。超时就是算法不高级，这个不用说了吧。还有一点在10^8内最大的回文素数是9989899（7位数），于是只需枚举到9999999（7位数），这样就节省了一大堆时间，也就不会超时了。A这道题的解法就是先单独写一个判断回文的函数；再判断素数时先筛掉偶数，再从奇数中进行筛掉一些合数（埃氏筛法），这样就不会用到int数组，内存也就不会超过限制了。

AC代码：

 #include<bits/stdc++.h>

 #define maxn 9999999

 using namespace std;

 bool isp[maxn];int a,b;

 bool is_palindrome(int n){//判断回文函数

     int sum=,tmp=n;

     while(tmp){sum=sum*+tmp%;tmp/=;}

     if(sum==n)return true;

     else return false;

 }

 int main(){

     memset(isp,true,sizeof(isp));

     isp[]=isp[]=false;

     for(int i=;i<maxn;i+=)isp[i]=false;

     for(int i=;i*i<maxn;i+=){//埃氏筛法

         if(isp[i]){

             for(int j=i*i;j<maxn;j+=*i)isp[j]=false;

         }

     }

     while(cin>>a>>b){

         for(int i=a;i<=b;i++){

             if(i>=maxn)break;

             if(isp[i]&&is_palindrome(i))cout<<i<<endl;//先判断素数,再判断回文数,效率更高

         }

         cout<<endl;//每组数据之后空一行

     }

     return ;

 }

秒客网