最后一个TLE

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

cza2023 @ 2023-12-26 12:56:09

#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return false;
    }
    return true;
}
bool ishuiwen(int n){
    string s=to_string(n);
    if(n>11&&s.size()%2==0&&n%11!=0)return 0;
    for(int i=0;i<s.size()/2;i++){
        if(s[i]!=s[s.size()-i-1])return false;
    }
    return isprime(n);
}
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(ishuiwen(i)&&i%2!=0)cout<<i<<endl;
    }
}

by Joker_Error_404 @ 2023-12-28 18:18:59

为什么我是MLE,我再看看

by cza2023 @ 2023-12-29 12:51:54

已经AC了，此贴结
顺便总结一下代码的不足：

  1. 在判断回文的过程中本身不必转为字符串，可以将数字本身倒一倒进行判断。代码如下 
    bool ishuiwen(int n){
int x=n,a=0;
while(x!=0){
    a*=10;
    a+=x%10;
    x/=10;
}
if(a==n)return isprime(n);
else return false;
}
  2. 10000000之后没有答案，可以在for循环直接break

by zuijiubugui @ 2024-01-03 20:24:44

深受启发楼主 我也是字符串写的 也是最后一点tle 感谢【玫瑰】

|