donghaoyu2011 @ 2023-02-08 17:18:48
还没评测就错了,样例输出多了一个9和121
#include <bits/stdc++.h>
using namespace std;
long long a,b,num[1000010];
bool find(long long x){
long long cc=0,res1=0,res2=0;
while(x!=0){
cc++;
num[cc]=x%10;
x/=10;
}
for(int i=1;i<=cc;i++){
res1*=10;
res1+=num[i];
}
for(int i=cc;i>=1;i--){
res2*=10;
res2+=num[i];
}
if(res1==res2){
return true;
}
else{
return false;
}
}
bool isprime(long long x){
if(x==1){
return false;
}
if(x==2){
return true;
}
for(int i=2;i<sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
int main(){
cin>>a>>b;
for(int i=a;i<=b;i++){
if(isprime(i)&&find(i)){
cout<<i<<endl;
}
}
return 0;
}
by donghaoyu2011 @ 2023-02-08 17:21:34
后来测了一下,33分。
by donghaoyu2011 @ 2023-02-08 17:22:18
要是开O2是44分
by olegekei @ 2023-02-08 17:28:27
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return false;
}
}
by donghaoyu2011 @ 2023-02-08 17:42:59
@olegekei 谢谢
by donghaoyu2011 @ 2023-02-08 17:46:05
@olegekei 但是TLE怎么解决,怎么优化
by olegekei @ 2023-02-08 17:51:24
@donghaoyu2011
把if(isprime(i)&&find(i))
改成if(find(i)&&isprime(i))
,另外读入的时候特判if(b>10000000) b=10000000;
by donghaoyu2011 @ 2023-02-08 17:57:16
@olegekei 谢谢,但能告诉我为什么要把 if(isprime(i)&&find(i))改成if(find(i)&&isprime) 吗?
by olegekei @ 2023-02-08 18:02:44
@donghaoyu2011 暴力check每一个数字是否是质数最坏是O(sqrt(n)),但是check每一个数字是否是回文数只需要O(a(≤7)),后者比前者快得多,
而把find放到isprime前面,程序会先执行find,如果find已经返回了false就不再进行isprime,大大优化了程序效率