之所以是上篇，当然是因为有下篇（bushi 有更优解。这里我们从最简单的角度一点点入手。

回顾原题如下： 

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

题目描述：
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围 [a,b] (5 <= a < b <= 100,000,000)（一亿）间的所有回文质数。

输入格式：
第一行输入两个正整数 a 和 b。

输出格式：
输出一个回文质数的列表，一行一个。

说明/提示：
提示 1: 找出所有的回文数再判断它们是不是质数（素数）.
提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

从最开始朴实无华的思路：在给定区间内遍历所有数，并判定是不是回文数和素数，是则输出。看起来很简单嘛~

当然不可能了，这样迎接你的将是赤裸裸的TLE。（P.S.做好准备哦，这道题TLE将常伴你）那咋办呢，我们先着手从两种数的判断优化入手。

对于素数判断，我们引入埃式筛法，先简单介绍一下它的筛选方法： 

1.创建一个从2开始到待查找范围上限（例如n）的整数列表，并初始化所有数字为“素数”状态。	
2.从最小的素数2开始，将它的所有倍数（除了它自身外）在列表中标记为非素数（通常是将其标记为0或删除）。	
3.找到下一个还没有被标记为非素数的数，假设它是p（即下一个素数），然后重复步骤2，将p的所有倍数（p×2, p×3, p×4, …）全部标记为非素数。	
4.继续这个过程，直到处理到√n为止（因为大于√n的数如果有因数的话，其对应的另一个因数必然小于等√n）。	5.最后，未被标记为非素数的数字就是所求范围内的素数。

这个方法并不难理解，而且在埃式筛法的优化下判断素数的时间复杂度来到了O(n log log n)，看起来已经省了一大半时间了。当然，此时提交仍然逃不过TLE的魔爪。

不妨再进一步想，对于能特判的例子都先特判节约时间，小于等于1必然不是素数，2是第一个素数，而大于二的偶数肯定不是素数，我们也没有必要对其验证，也不用他们作为判断某数（我们定义为n）的因子。所以对于1，2，大于2的偶数一律特判，从3开始遍历到根号n，步长为2（这样，每次判定的因子都是奇数，又省一点时间）。

所以在我们绞尽脑汁的优化下，写出了判定素数的代码。 

bool is_prime(int n)
{
    if(n<=1) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    // 只需要检查到sqrt(n)
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

很好，还是TLE…

还有什么能优化的吗？回文数的判断是不是可以进一步缩减时间？通常情况下，我们想到最优的方法就是假设判断的数n是回文数，通过取出各个位置的数字构造一个回文数，判断构造数与原数是否相等。不过沿着特判的思路想，我们不难发现10以内的自然数都是回文数，10的倍数（当然包括他自己）都不是回文数，因为没有数能以0作为前导。好，那么我们很快得到了回文数的判断代码。 

bool is_pal(int n)
{
    if(n<10) return true;
    if (n % 10 == 0) return false;
    int reversed = 0;
    int original = n;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return reversed == original;

}

接下来着手处理主程序了。先引入一个加速输入输出的方法。 

ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

继续我们的特判大业，根据上文中偶数的判定，我们可以进一步缩减便利区间：当给的起始值n为偶数，遍历区间start从n+1开始，如果n是奇数，首先确保n大于等于3，此时可以先输出2，也是唯一的偶素数。如果n小于3，那就可以直接结束了。

确定了判定区间的起始值为奇数，我们可以只对区间内的所有奇数进行判定，设置遍历的步长为2。此时基本算是大功告成，我们不妨用最极端的数据看看情况：用我们的代码输出从1到一亿中所有的回文素数，编译，运行，然后一股脑拉到终端输出的最后一行，上面赫然写着：9989900。

一切明了，在数据范围内最极端的也就是到这个值，所以哪怕是遍历结束值为一亿，我们实际上也只需要到这个值就可以停止判定了。

费尽九牛二虎之力，我们终于憋出了主函数的代码。 

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n,m;
    cin>>n>>m;
    if (n <= 2 && m >= 2) {
        cout << 2 << endl;
    }
    int start;
    // 判断n是否是偶数
    if (n % 2 == 0) {
        // 如果n是偶数，就从n+1开始（跳过偶数）
        start = n + 1;
    } else {
        // 如果n是奇数，就从n开始，但至少要大于等于3
        // 因为2是唯一的偶质数，我们已经单独处理过了
        if (n < 3) {
            start = 3;  // 确保从3开始
        } else {
            start = n;   // 从n开始
        }
    }
    for(int j=start;j<=m;j+=2)
    {
        if(j==9989900) //如果到了这个数，就break 
		{
		    break;
		}
        if (!is_pal(j)) continue;
        if(is_prime(j)){
            cout<<j<<endl;
        }
    }
    return 0;
}

很好，此时提交就不会出现折磨了你n次的TLE了，不过记得把O2优化打开，不然可能还是会TLE。

你长舒一口气：呼，终于把烦人的回文素数搞定了。不过就在你关掉电脑，一个念头闪过你的脑海：

能不能正向思维一下，通过【构造】的方法进行呢……