大家，为什么会超时呀这个

adksla @ 2024-01-03 15:48:43

# include<iostream>
# include <cstring>
#include<math.h>
using namespace std;

int zs(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}

int hw(int num){
    int t=num,ans=0;
    while(t){
        ans = ans*10 + t%10;
        t/=10;
    }

    if(num==ans) return 1;
    else return 0;
}

int main()
{   
    int a,b;
    cin >> a >> b;
    for(int i=a;i<=b;i+=2){
        if(zs(i)){
            if(hw(i)){
                cout << i << endl;
            }
        }
    }

    return 0;
 } 

by xzh_2013 @ 2024-01-03 15:57:08

@adksla

时间复杂度 O(sn\sqrt n) （ s 为 b 的长度），约为 O(900000000000) ,吸氧估计也没用

by xzh_2013 @ 2024-01-03 15:58:54

@adksla 把两个 if 换一下就好了吧

by xzh_2013 @ 2024-01-03 16:01:44

@adksla i+=2 那个优化不能要

by xzh_2013 @ 2024-01-03 16:04:19

@adksla 你看一下，改了就A了，还要加一个是否是偶数的特判，复杂度 O(\displaystyle \frac{sn\sqrt n}{2})

by 崔化博 @ 2024-01-03 16:19:43

@xzh19386551361 复杂度不是这个吧，复杂度分开算，只判回文是log的，是回文的才会判质数而回文数只有约2*(10+10^2+10^3+10^4)个(约10^4个)，加上判断质数的时间。

复杂度O(10^4\sqrt b +blog_{10}b)，加上跑不满，是可以过的

by 崔化博 @ 2024-01-03 16:21:53

而如果按lz那样的话，应该是b \sqrt b+b的（质数只有n/log个，加上log的判断）

by 崔化博 @ 2024-01-03 16:23:00

额，好像不能带常数，小问题

by xzh_2013 @ 2024-01-03 16:34:11

@崔化博 也是 （雾

by adksla @ 2024-01-03 17:24:44

@xzh19386551361 明白了，感谢！

by adksla @ 2024-01-03 17:25:39

# include<iostream>
# include <cstring>
#include<math.h>
using namespace std;

int zs(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}

int hw(int num){
    int t=num,ans=0;
    while(t){
        ans = ans*10 + t%10;
        t/=10;
    }

    if(num==ans) return 1;
    else return 0;
}

int main()
{   
    int a,b;
    cin >> a >> b;
    if(a%2==0) a++;
    for(int i=a;i<=b;i+=2){
        if(hw(i)){
            if(zs(i)){
                cout << i << endl;
            }
        }
    }

    return 0;
 } 

@崔化博 谢谢你，改成这样就过啦我