88分求助!1个TLE!

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

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

dalao们帮我看一下这个代码,为啥会TLE呀(最后一个样例TLE了)?感谢

#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-17 12:31:44

@Yue_Hao 炸时,for套while,套for


by simple_child @ 2024-08-17 12:32:19

@Yue_Hao 而且剪枝也不多


by Yue_Hao @ 2024-08-17 12:36:18

@simple_child ,我没学剪枝(悲......)


by Yue_Hao @ 2024-08-17 12:37:56

@simple_child ,那怎么办啊,dalao,我能想到的最优只有这个了,如果判断偶数位回文,我直接0分了


by simple_child @ 2024-08-17 12:37:58

@Yue_Hao 就是优化,把一些无用计算过滤掉


by simple_child @ 2024-08-17 12:42:18

@Yue_Hao 埃氏筛你会吗


by simple_child @ 2024-08-17 12:42:52

@Yue_Hao 这题数据水,没有偶数位回文


by Yue_Hao @ 2024-08-17 12:44:17

@simple_child ,还能再优化吗?是不是判断偶数位数字不是回文数(11除外)然后去掉一半的for循环?


by Yue_Hao @ 2024-08-17 12:45:12

@simple_child ,可是这样只能55分,并且第二个测试点还会多出一个10201是怎么回事啊?


by simple_child @ 2024-08-17 12:46:08

@Yue_Hao 可能是的,这题我也没做((


| 下一页