66分TLE求救

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

wanghonghui123 @ 2024-07-20 12:19:17

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline bool isPrime(LL x){
    if(x<2) return false;
    for(LL i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    LL a,b;
    cin>>a>>b;
    for(LL i=a;i<=b;i++){
        string s=to_string(i);
        string t=s;
        reverse(s.begin(),s.end());
        if((isPrime(i))&&(s==t)){
            cout<<i<<endl;
        }   
    }
    return 0;
}

by dongzirui0817 @ 2024-07-20 12:24:09

@wanghonghui123 注意数据范围 1\le a, b \le 100,000,000\ 你这样时间复杂度不对


by wanghonghui123 @ 2024-07-20 12:26:35

@dongzirui0817 那复杂度因该是什么?


by dongzirui0817 @ 2024-07-20 12:37:39

这样时间复杂度大概为 O((b-a) \times \sqrt b) 这样筛回文数不行,可以去借鉴一下题解,那里边筛回文数会比这样快。


by wanghonghui123 @ 2024-07-20 16:42:25

@dongzirui0817 OK


by Allen20 @ 2024-07-21 09:19:44

先回文判断再质数判断


|