最后三个测试点一直TLE应该怎么办

MAOSICHENG @ 2023-05-06 23:21:07

#include<iostream>
#include<string>
#include<cstring>
#include<math.h>
using namespace std;
int Prime(int a) {
    if (a < 2) return 0;
    if (a > 2) {
        for (int i = 2; i <= sqrt(a); i++) {
            if (a % i == 0) {
                return 0;
            }
        }
    }
    return a;
}
int main() {
    int n, m;

    cin >> n >> m;
    for (int i = n; i <= m; i++) {
        if (Prime(i) != 0) {
            bool isPalindrome = true;
            int num = i;
            string str = to_string(i);
            for (int j = 0; j < str.size() / 2; j++) {
                if (str[j] != str[str.size() - 1 - j]) {
                    isPalindrome = false;
                    break;
                }
            }
            if (isPalindrome) {
                printf("%d\n",i);
            }
        }
    }
}

by liuzikun___ @ 2023-05-07 09:01:20

@MAOSICHENG 会超时是因为可以进入循环的质数太多了，建议回文数和质数都写成函数，然后先判断回文数

by liuzikun___ @ 2023-05-07 09:03:33

@MAOSICHENG 但是按我这样写的话最后一个点还是会超时，但开O2就满分了

by Loic_ @ 2023-05-07 09:43:34

暴力 O(n\sqrt{n}) 能过就有鬼了。建议先去学习一下时间复杂度。

by MAOSICHENG @ 2023-05-07 09:49:17

@XH_yyds 谢谢

by MAOSICHENG @ 2023-05-07 09:50:08

@Loic_ 刚开始学编程,阿巴阿巴

by qwiwiiwjjdks @ 2023-07-02 14:27:02

看我的入门级代码，也是刚入门

#include<bits/stdc++.h>
using namespace std;
bool pdzs(int n){
    if(n<2) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}
bool h(int n){
    int y = 0,k = n;
    while(n>0){
        y = y*10+n%10;
        n = n/10;
    }
    if(y==k) return true;
    else return false;
} 
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(i>9989899) return 0;
        else{
            if(i!=2 && i%2==0) continue;
            else if(h(i)){
            if(pdzs(i)) printf("%d\n",i);
            }
            else continue;
        }

    }
    return 0;
}