HDU1431

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1431

此题可先求10^8以内的最大回文素数，大概用时250秒- -，求得最大回文素数为：9989899，代码如下：

// Note:Your choice is C++ IDE
#include <iostream>
using namespace std;
#include<time.h>
#include<math.h>
int is_p(int n)
{
    int i,m;
    m=(int)(sqrt(n*1.0));
    for(i=2;i<=m;i++)
     if(n%i==0)return 0;
     return 1;
}
int is_hui(int n)
{
    char s[10];
    sprintf(s,"%d",n);
    int l=strlen(s);
    for(int i=0;i<l/2;i++)
     if(s[i]!=s[l-1-i])
     return 0;
    return 1; 
    
}
int main()
{
    for(int i=100000000;i>=0;i--)
    if(is_p(i)&&is_hui(i))
    {
        printf("%d\n",i);
        break;
    }
    printf("%.2lf\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

所以在此范围内按常规思路求解即可，不会超时，还有用筛选法判断素数时，用bool型，否则会超内存。

AC代码如下：

#include <iostream> //求得最大回文素数为:9989899
using namespace std;
#include<math.h>
#define M 9989899
bool a[M+1]={0};//用bool型可以不超内存
int p[1000000],h[1000];
int k=0,k1=0;
void is_p() //筛选法判定素数
{
    int i,j,m;
    m=(int)(sqrt(M*1.0));    
    for(i=2;i<=m;i++)
     if(!a[i])
     for(j=i*i;j<=M;j+=i)
      a[j]=true;
     for(i=5;i<=M;i++)
      if(a[i]==false)
      p[k++]=i;
       
}
void is_hui()//判断回文数
{
    int i,j;
    char s[10];
    for(i=0;i<k;i++)
     {
         int q=1;
         sprintf(s,"%d",p[i]);
         int l=strlen(s);
         for(j=0;j<l/2;j++)
          if(s[j]!=s[l-1-j])
          {
              q=0;
              break;
          }
          if(q)h[k1++]=p[i];
     }
}
int main()
{
     is_p();
     is_hui();
     //cout<<k<<endl<<k1<<endl;
     int a,b;
     while(scanf("%d%d",&a,&b)!=EOF)
     {
         if(b>M)b=M;
         for(int i=0;i<k1;i++)
         {
             if(h[i]>b)break;
          if(h[i]>=a)cout<<h[i]<<endl;          
         }
         cout<<endl;
     }
    return 0;
}