算法1

(暴力枚举) $O(n)$

枚举所有回文数一共$\sqrt{n}$个，判断是否为素数，每次判断$\sqrt{n}$，总复杂度$\sqrt{n}$*$\sqrt{n}$即$O(n)$;

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 3e5+5;
int mod = 1e9 +7;
int n,m,k;
int p[15];
//求该数的回文数？d为0沿最后一个数对称，d为1直接对称
int get(int x,int d){
    int t = x;
    int k = 0,cur = 0;
    //求位数k，镜像数字cur
    while(t){
        cur = cur * 10 + t % 10;
        k++;
        t /= 10;
    }
    if(!d){
        //x左移k - 1位
        x *= p[k - 1];
        //cur去掉最高位
        x += cur % p[k - 1];
    }
    else{
        x *= p[k];
        x += cur;
    }
    return x;
}
//判断素数
bool check(int x){
    if(x < 2) return false;
    for(int i = 2 ; i <= x / i ; ++i ){
        if(x % i == 0) return false;
    }
    return true;
}
//先跑第一种对称再跑第二种对称
void run(int l,int r){
    for(int i = l ; i <= r ; ++i ){
        int t = get(i,0);
        if(t < n) continue;
        if(t > m) return;
        if(check(t)) cout << t << endl;
    }
    for(int i = l ; i <= r ; ++i ){
        int t = get(i,1);
        if(t < n) continue;
        if(t > m) return;
        if(check(t)) cout << t << endl;
    }
}
void solve(){
    p[0] = 1;
    for(int i = 1 ; i <= 10 ; ++i) p[i] = p[i - 1] * 10;
    cin >> n >> m;
    //按位数跑
    run(1,9),run(10,99),run(100,999),run(1000,9999);
}

signed main(){
    IOS;
    solve();
    return 0;
}