shan_hai_wind @ 2024-10-11 10:29:44
#include <bits/stdc++.h>
using namespace std;
// 检查一个数是否为质数
bool isPrime(int num) {
if (num == 2) return true; // 2 是质数
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
// 检查一个数是否为回文数
bool isPalindrome(int num) {
int original = num;
int reversed = 0;
while (num) {
reversed = reversed * 10 + num % 10;
num /= 10;
}
return original == reversed;
}
int main() {
int a, b;
scanf("%d %d",&a,&b);
if(a == 2) printf("2\n");
if(a%2 == 0) a++;
for (int i = a; i <= b; i=i+2) {
if (isPrime(i) && isPalindrome(i)) {
printf("%d\n",i);
}
}
return 0;
}
by coding_goat @ 2024-10-11 10:34:24
@shan_hai_wind 兄弟,你光是循环从
然后就是你判断他是否是质数的时间复杂度是
by Melo_DDD @ 2024-10-11 10:43:14
@coding_goat 其实跑不到
@shan_hai_wind 但是楼上正解,
by shan_hai_wind @ 2024-10-11 10:49:46
可以过,我只要利用&&,先判断回文数就行了
by lihaoda @ 2024-10-11 10:51:08
@shan_hai_wind 怎么说一瞪眼肯定是
by shan_hai_wind @ 2024-10-11 10:52:04
@coding_goat 换一下&&两边函数,先判断回文会快很多,就可以过
by coding_goat @ 2024-10-11 10:58:15
@shan_hai_wind 是这样的,因为回文数个数少而且你循环跑不满
by coding_goat @ 2024-10-11 10:59:14
@coding_goat 如果想从时间复杂度上优化可以打表/学习 Miller-Rabin 素性测试
by shan_hai_wind @ 2024-10-11 11:49:25
@coding_goat 好的,谢谢你