66分TLE……改scanf、printf依旧不行，求调（不会打表、算法啊……）

zhenshijuruo @ 2024-08-11 10:52:44

#include<bits/stdc++.h>
using namespace std;
bool sushu(int n) {
    if(n<=1)return false;
    for(int i=2; i<=sqrt(n);i++) {
        if(n%i==0)return false;
    }
    return true;
}
bool huiwen(int n) {
    int a=n,b=0,c;
    while(n!=0) {
        c=n%10;
        b=b*10+c;
        n/=10;
    }
    return a==b;
}
int main() {
    int a,b;
    scanf("%d%d",&a,&b);
    for (int i=a;i<b;i++) {
        if (sushu(i) && huiwen(i)) {
            printf("%d\n",i);
        }
    }
    return 0;
}

by _zhang @ 2024-08-11 10:59:41

@gsr_2014 O(n \sqrt{n} )的复杂度不TLE才怪呢

by _zhang @ 2024-08-11 11:02:46

我的想法是构造回文数再判断素数

by CSQ7 @ 2024-08-11 11:08:58

然后不要枚举位数为偶数的，mod11

by CheeseFunction @ 2024-08-11 11:19:24

按理来讲，这时间复杂度也不高，罪不致TLE，但是你的代码框架不是很好，思想稍微有点点误差，我按你的思想写了一份代码，A了，你可以看看:

#include<bits/stdc++.h>
using namespace std;
int prime(int x){
    if(x==1)return true;
    for(int i=sqrt(x);i>=1;i--){
        if(x%i==0 && i!=1)return true;
    }
    return false;
}
int main(){
    int a,b,zx[100]={0},nx[100]={0};
    cin>>a>>b;
    if(a==2){
        cout<<2<<endl;
        a++;
    }else if(a%2==0)a++;

    for(int i=a;i<=b;i+=2){
        int i1=i;
        bool sum=true;
        int js=0;
        while(i1){
            js++;
            zx[js]=i1%10;
            nx[js]=i1%10;
            i1/=10;
        }
        reverse(nx+1,nx+js+1);
        while(js--){
            if(nx[js]!=zx[js])sum=false;
        }
        if(sum && !prime(i)){
            cout<<i<<endl;
        }
    }
}

by zhenshijuruo @ 2024-08-11 20:15:02

@FearlessWarriors 知道了，谢谢大佬！

by zhenshijuruo @ 2024-08-11 20:35:58

@_zhang （不会算时间复杂度（哭））明白啦，我会注意的！！！

by zhenshijuruo @ 2024-08-11 20:42:13

@CSQ7 (恍然大悟）原来还可以这样做！谢谢大佬！

by zhenshijuruo @ 2024-08-11 20:44:09

这道题我是终于AC了，非常感谢各位大佬的指点！！！

by lizan7 @ 2024-08-24 16:56:11

@FearlessWarriors 大佬我认为我的代码跟你的基本一样，但是有3个超时，这是为啥；

#include<bits/stdc++.h>
using namespace std;
bool sushu(int a){
    for(int j=2;j<=(int)sqrt(a);j++)
        {
            if(a%j==0)return false;
        }//质数部分 
    return 1;
}
int main(){
    int a,b,c1,c2;
    cin>>a>>b;
    if(a%2==0)a++;
    for(int i=a;i<=b;i+=2)
    {
        int hui=1,cnt=0;
        int num1[20],num2[20];
        int ii=i;
        while(ii!=0)
        {
            num1[cnt]=ii%10;
            num2[cnt]=ii%10;
            ii/=10;
            cnt++;
        }
        reverse(num1,num1+cnt);
        for(int j=0;j<cnt;j++)
        {
            if(num1[j]!=num2[j])hui=0;
        }
        if(sushu(i)&&hui)cout<<i<<endl;
    }
    return 0;
}//2024.8.24