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

题目链接：https://www.luogu.org/problemnew/show/P1217

说起来你可能不信，这是洛谷新手村的一道题目…1e9这么大数据吓了我一跳

我刚开始看这题还以为要写素数筛，后来看了一下说明，woc！直接枚举个位数、十位数、百位数生成回文数再判断 （我怎么开始就没想到）

AC代码略长，思路很简单。

#include <bits/stdc++.h>
using namespace std;
int a,b,s,cnt,pos[1010];//pos记录回文质数
bool judge(int x)//没错，只需要这种最朴素的判断素数函数，欧拉线性素数筛都不需要！
{
    if(x==1)return 0;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    for(int d1=1;d1<=9;d1++)
    {
        if(judge(d1))pos[++cnt]=d1;//1位回文数
        if(judge(d1+10*d1))pos[++cnt]=d1+10*d1;//2位回文数
    }
    for(int d1=1;d1<=9;d1=d1+2)//个位数为偶数不可能是素数，d1=d1+2
    {
        for(int d2=0;d2<=9;d2++)
        {
            s=100*d1+10*d2+d1;
            if(judge(s))pos[++cnt]=s;//3位回文数
            s=1000*d1+100*d2+10*d2+d1;
            if(judge(s))pos[++cnt]=s;//4位回文数
        }
    }
    for(int d1=1;d1<=9;d1=d1+2)
    {
        for(int d2=0;d2<=9;d2++)
        {
            for(int d3=0;d3<=9;d3++)
            {
                s=1e4*d1+1e3*d2+1e2*d3+1e1*d2+d1;
                if(judge(s))pos[++cnt]=s;//5位回文数
                s=1e5*d1+1e4*d2+1e3*d3+1e2*d3+1e1*d2+d1;
                if(judge(s))pos[++cnt]=s;//6位回文数
            }
        }
    }
    for(int d1=1;d1<=9;d1=d1+2)
    {
        for(int d2=0;d2<=9;d2++)
        {
            for(int d3=0;d3<=9;d3++)
            {
                for(int d4=0;d4<=9;d4++)
                {
                    s=1e6*d1+1e5*d2+1e4*d3+1e3*d4+1e2*d3+1e1*d2+d1;
                    if(judge(s))pos[++cnt]=s;//7位回文数
                    s=1e7*d1+1e6*d2+1e5*d3+1e4*d4+1e3*d4+1e2*d3+1e1*d2+d1;
                    if(judge(s))pos[++cnt]=s;//8位回文数
                }
            }
        }
    }
    sort(pos+1,pos+cnt+1);//cnt=781
    cin>>a>>b;
    for(int i=1;i<=cnt;i++)
    {
        if(pos[i]>=a&&pos[i]<=b)printf("%d\n",pos[i]);
        if(pos[i]>b)break;
    }
    return 0;
}