88分求助!1个TLE!

Yue_Hao @ 2024-08-17 12:26:51

#include <bits/stdc++.h>
using namespace std;
bool pd(long long n){
    for(long long i = 3; i <= ceil(sqrt(n)); i += 2) if(n % i == 0) return false;
    return true;
}
bool reint(long long n){
    long long nn = n;
    string s = "", c;
    while(nn != 0){
        c = (nn % 10 + '0');
        s.insert(0, c);
        nn /= 10;
    }
    string s1 = s;
    reverse(s1.begin(), s1.end());
    if(s1 == s){
        if( pd(n) ) return true;
        else return false;
    }else return false;
}
int main(){
    long long a, b;
    scanf("%lld %lld", &a, &b);
    if(a % 2 == 0) a += 1;
    for(long long i = a; i <= b; i += 2) if( reint(i) ) printf("%lld\n", i);
    return 0;
}

by simple_child @ 2024-08-18 10:49:39

@Yue_Hao 那就得重构了（（（

by chenbingjie @ 2024-08-18 11:19:38

我用过埃氏筛法，最后也会TLE

 #include<bits/stdc++.h>
using namespace std;
bool pri[100000010];
void prime(int d) {
    memset(pri,true,sizeof(pri));
    pri[1]=false;
    for(int i=2;i<=d;i++){
        if(pri[i]){
            for(int j=2;j<=d;j++){
                if(i*j>d)break;
                pri[i*j]=false;
            }
        }
    }
}
bool check_hui(int d) {
    string h=to_string(d);
    string t=h;
    reverse(t.begin(),t.end());
    if(t==h)return true;
    else return false;
}
int main() {
    int a,b;
    cin>>a>>b;
    prime(b);
    if(a%2==0)a++;
    for(int i=a;i<=b;i+=2){
        if(pri[i]&&check_hui(i))cout<<i<<endl;
    }
    return 0;
}

by chenbingjie @ 2024-08-18 11:21:12

@simple_child

by Yue_Hao @ 2024-08-18 11:50:15

@simple_child dalao,我也只能重构到这里了

by xizao_haoxuan @ 2024-08-19 11:33:34

@Yue_Hao 最后一个测试点要用欧拉筛

by xizao_haoxuan @ 2024-08-19 11:35:49

@Yue_Hao a和b可以就用int类型

by xizao_haoxuan @ 2024-08-19 11:36:28

i也是

by xizao_haoxuan @ 2024-08-19 11:38:00

@Yue_Hao 我在讨论版里发了欧拉筛法（质数筛）

by xizao_haoxuan @ 2024-08-19 11:42:57

@chenbingjie 要用欧拉筛

by xizao_haoxuan @ 2024-08-19 11:46:43

@Yue_Hao 我再私信发给你一遍