为什么最后一个测试点总是TLE，还有什么优化方式呢？怎样优化求质数呢？

Zzz123456789101112 @ 2024-03-05 18:15:03

#include<iostream>
#include<math.h>
using namespace std;
int digit(int  x) {//判断是否为>2的偶数位数的数，若是则没有回文质数，因回文数均为11的倍数
    if ((x >= 1000 && x <= 10000) || (x >= 100000 && x <= 1000000))
        return 0;
    else
        return 1;
}
int reverse(int x) {//判断是否为回文数（借用翻转函数的思路）
    int result = 0;
    int num = x;
    while (x != 0) {
        result = result * 10 + x % 10;
        x /= 10;
    }
    if (result == num)
        return 1;
    else
        return 0;
}
int IsPrime(int x) {

        for (int i = 2; i <= (int)sqrt(x); i++) {//如果n被i整除，则返回false
            if (x % i == 0) {
                return 0;
            }
        }
        return 1;    // 反之则返回true 

}
int main() {
    int a, b;
    cin >> a >> b;
    if (a < 5 || b>1000000000) {
        return 0;
    }

    for (int  i = a; i <= b; i++) {//
        //if (i == 9999989) //如果到了这个数，就break 
        //  break;//?必须判断吗？i<=b不能作为返回条件吗？
        if (digit(i) &&reverse(i)&&  IsPrime(i) ) {
            cout << i<<endl;
        }
    }
    return 0;
}

by HEROBRINEH @ 2024-03-05 18:16:03

亲测AC

#include<bits/stdc++.h>
using namespace std;
bitset<100000001>z;
int zs[5000000],a,b,y,o,u;
int zx,zd;
int find(int l,int r,int k){  
    int m;
    while(l+1<r){
        m=(l+r)/2;
        if(zs[m]<=k)l=m;  
        else r=m;       
    }
    if(k-zs[l]<=zs[r]-k)return l;
    else return r;
} 
void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
int main(){
    a=read(),b=read();
    zs[1]=2,y=1;
    for(int i(3);i<=b;i+=2){
        if(z[i]==1)continue;
        y++,zs[y]=i,o=i<<1;
        for(int j(i+o);j<=b;j+=o)z[j]=1;
    }
    zx=find(1,y,a);zd=find(1,y,b);
    for(int i(zx);i<=zd;i++){
        o=zs[i],u=0;
        while(o>0){
            u*=10;
            u+=o%10;
            o/=10;
        }
        if(zs[i]==u)write(zs[i]),printf("\n");
    }
    return 0;
}

by Zzz123456789101112 @ 2024-03-05 18:28:30

@HEROBRINEH 源代码上有什么建议吗