hdu 1431 素数回文（暴力打表，埃托色尼筛法）

这题开始想时，感觉给的范围5 <= a < b <= 100,000,000太大，开数组肯定爆内存，而且100000000也不敢循环，不超时你打我，反正我是不敢循环。

这题肯定得打表，筛素数肯定用埃托色尼筛法（不好意思把大名鼎鼎的埃拉托色尼名字打错了，表打我）。

再看当你所找的回文数的位数为偶数时，有如下定理除11外所有偶数位数的回文数都能被11整除，所以所有偶数位数的回文都不是素数。

证明看如下（我手写的）

手机像素渣（凑活着吧）字丑也凑和着。

证完后我们在来说题目给的数据范围

所以当有8位时都不可以，所以数据缩小为999999；

那么下面就用素数筛法直接打表就行了。

然后再开个数组存回文的素数。

但是一开始我是用int开数组来筛素数的，不得不说傻逼了，内存爆到家了，我一开始很郁闷，这咋爆了呢，我靠，后来一想int型占4个字节，改成bool型的

哈哈，没爆，过了，bool型占一字节，所以内存果断下降4倍。我以前一直开int型的。我煞笔本来准备开longlong 的，估计要爆到姥姥家。

下面看代码：

#include<stdio.h>
bool a[9989900]={0};
int pp(int n);
int dd[1000];//素数回文数组本来以为会很大，但却很少，可以先打表看看。
int main(void)
{
    int n,i,j,k,p,q;
    a[0]=true;
         a[1]=true;
    for(i=2; i<4000; i++)
    {
        if(a[i]==0)
        {
            for(j=i; i*j<9989900; j++)
            {
                a[i*j]=true;
            }
        }
    }//素数筛选暴力打表
    int kk=0;
int t=0;
    for(i=5;i<9989900;i++)
    {
        if(!a[i]&&pp(i))
        {
            dd[t++]=i;
        }
    }//选出回文加入数组

    while(scanf("%d %d",&p,&q)!=EOF)
    {for(i=0;i<t;i++)
    {
        if(dd[i]>=p&&dd[i]<=q)
        {
            printf("%d
",dd[i]);
        }
        if(dd[i]>q)
        {
            break;
        }
    }
printf("
");
    }

return 0;


}

int pp(int n)//判断回文，正着和反着数值大小都一样
{
    int i;
    int y=0;int yy=n;int uu=1;
    while(n>0)
    {
        y=y*10+n%10;
        n=n/10;
    }

    if(y==yy)
    {
        return 1;
    }
    return 0;
}