题目描述

简单来说，就是给你一个区间，找出这个区间内所有的素数，并判断是不是回文数。

具体实现

判断回文数的方法很简单。代码如下：

bool pd_h(int x)
{

    int y = x, num = 0;
    while (y != 0)
    {
        num = num * 10 + y % 10;
        y /= 10;
    }
    if (num == x)
        return true;
    else
        return false;
}

这道题要解决的是怎么求出指定区间内的素数。关于暴力求解的方法另一篇题解中已经有了。在此不多作赘述。
其实，求解给定区间内的素数常用的方法是一种时间复杂度为O(n)的方法，称为欧拉筛。
关于欧拉筛的介绍，可以参考下面的文章
筛法
然后再回到这一题，上面我们已经有了判断是不是回文数的方法，下面要做的就是使用欧拉筛法求出给定区间内的所有素数。
代码如下：

for (int i = 2; i <= b; i++)
{
    if (!vis[i])
        prime[cnt++] = i, pp[i] = 1;
    for (int j = 0; j < cnt && i * prime[j] <= b; j++)
    {
        vis[i * prime[j]] = i;
        if (i % prime[j] == 0)
            break;
    }
}

下面给出本题的AC代码：

#include <iostream>
#include <cstdio>
#define MAXN 10000005
using namespace std;
int prime[MAXN];
bool pp[MAXN];
int vis[MAXN];
bool pd_h(int x)
{

    int y = x, num = 0;
    while (y != 0)
    {
        num = num * 10 + y % 10;
        y /= 10;
    }
    if (num == x)
        return 1;
    else
        return 0;
}
int main(int argc, const char *argv[])
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    if (b > 10000000)//这里是10^7 不是10^8，那题目给的是10^8为什么10^7可以过呢。
        b = 10000000;//这里涉及到一个知识，任何偶数位数的回文数都不是素数（11除外），原因可以百度。其实就是偶数位数的回文数可以被11整除，所以不会是素数
    for (int i = 2; i <= b; i++)
    {
        if (!vis[i])
            prime[cnt++] = i, pp[i] = 1;
        for (int j = 0; j < cnt && i * prime[j] <= b; j++)
        {
            vis[i * prime[j]] = i;
            if (i % prime[j] == 0)
                break;
        }
    }
    for (int i = a; i <= b; i++)
    {
        if (i > 10000000)
            break;
        if (pd_h(i) && pp[i])
            printf("%d\n", i);
    }
    return 0;
}