一种非打表的超快速解法

嗯......要找大量质数，所以当然使用埃拉托斯特尼筛法对吧

然而要找先找到一亿以内的质数实在还是太慢了，并且我决定不判断是否是回文数，而是直接生成回文数。

最值得注意的是回文数生成有两种，偶数长度和奇数长度，举例：在5、6长度下的回文数，用于生成回文数的原数长度就是3（(n+1)/2），例如123可以生成12321和123321两个回文数。

于是我写了一个带有模式参数的 mirroring 函数，在调用的时候交替调用两种模式即可保证先生成的总是更小的数

既然回文数直接生成出来了，那么需要判断质数的数量就大大减少了，此时只需要用常规的办法判断质数

先判断完小数字并排除 2 和 3 的所有倍数，剩下的所有数都是 6n±1 的数，而且i仅需要判断到n的平方根就行了，i<=sqrt(n) 进行了浮点运算，会浪费大量时间，所以要用 i*i<=n 进行循环判断

至此就得到了相当优的解，总耗时 49ms，耗时仅仅是打表 27ms 的1.8倍，内存占用基本与打表相同

下面是代码：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int n){
    if(n<=1) return 0;
    if(n<=3) return 1;
    if(n%2==0 || n%3==0) return 0;
    for (int i=5;i*i<=n;i+=6)
        if(n%i==0 || n%(i+2)==0)
            return 0;
    return 1;
}
// mode=0 生成偶数位回文数 mode=1 生成奇数位回文数
int mirroring(int a,bool mode){ 
    int len=log10(a)+1;
    a*=pow(10,len-mode);
    for(int i=1;i<=len-mode;i++)
        a+=(int(a/pow(10,2*len-i-mode))%10)*pow(10,i-1);
    return a;
}
void Palindromes(int n,int a,int b){
    ios::sync_with_stdio(false);
    for(int i=1;i<=n;i++){
        int start=pow(10,(i+1)/2-1);
        int end=pow(10,(i+1)/2);
        bool mode=i%2;
        for(int j=start;j<end;j++){
            int num=mirroring(j, mode);
            if(num>=a && num<=b && isPrime(num)==1)
                cout<<num<<endl;
        }   
    }
}
int main() {
    int n,a,b;
    cin >> a >> b;
    // n 代表最大位数，也就是b的位数
    n=min(int(log10(b)+1),8);
    Palindromes(n,a,b);
}