@[XDYZ_N](/user/1236269)
每一个数都枚举的话复杂度逼近甚至超过 $O(10^8)$ ，有一部分的数据会超时
by lunjiahao @ 2024-02-21 21:40:02
一个回文数的位数为偶数不为质数（除11以外）
by lunjiahao @ 2024-02-21 21:42:01
ACcode:
```cpp
#include<bits/stdc++.h>
using namespace std;
int qw(int p){
int q=p,m=0,a=p;
while(a){
m = m*10+a%10;
a /= 10;
}
if(q==m) return 1;
else return 0;
}
int as(int m)
{
for(int i=2;i<=sqrt(m);i++){//判断素数只需枚举2~sqrt(m)是否有数为m的因数即可
if(m%i==0){
return 0;//这里的return 0会直接返回主程序，无需break
}
}
return 1;
}
int main()
{
int a,b;
cin>>a>>b;
if(b>9999999) b=9999999;//优化枚举最大值，回文质数在本题中最多只有7位且为奇数
if(a==2) cout<<a<<endl;//特判2这个质数中唯一的偶数
if(a%2==0) a++;//从奇数开始
for(int i = a;i<=b;i+=2)//因为偶数（除了2以外）都不会是质数，所以枚举奇数
{
if(qw(i) == 1)
{
if(as(i) == 1)
{
cout<<i<<endl;
}
}
}
return 0;
}
```
by lunjiahao @ 2024-02-21 21:52:27
时间复杂度约为 $O(n\log n)$，其中 $n$ 最大为 $5\times10^6$
by lunjiahao @ 2024-02-21 21:55:02
```java
package com.lianxi;
import java.util.Scanner;
public class P1217 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
for (int i = a; i <= b; i++) {
int temp = i;
int result = 0;
int ans=huiWen(i);
if(ans==temp) {
boolean flag = true;
for (int j = 2; j < temp; j++) {
if (temp % j == 0) {
flag = false;
break;
}
}
if(flag){
System.out.println(temp);
}
}
}
}
public static int huiWen(int i) {
int result=0;
while (i != 0) {
int ge = i % 10;
result = result * 10 + ge;
i /= 10;
}
return result;
}
}
```我也是超时，最后三个，大佬看看
by zhu5001210249 @ 2024-02-21 21:59:08
@[lunjiahao](/user/779970) 大佬看看
by zhu5001210249 @ 2024-02-21 22:00:02
首先，你判素数的函数是$O(n)$的，每个数枚举，相当于$O(n^2)$，不$\text T$就有鬼了
其次，就算你判素数的函数是$O(\sqrt n)$的，整体复杂度最坏是$O(n\sqrt n+n\log n)$，还是容易$\text T$
这题我用的是欧拉筛+判断回文，时间复杂度$O(n+\displaystyle\frac{n\log n}{\ln n})$，后面那段不超过$O(n)$，所以整体是$O(n)$，稳稳不会$\text T$
@[XDYZ_N](/user/1236269)
by QWQ_HY_DFX @ 2024-02-21 22:01:48
@[lunjiahao](/user/779970)
理论最坏时间复杂度为$O(n\sqrt n+n\log n)$，不过可能因为回文素数数量稀少，所以整体时间复杂度为$O(n\log n+k\sqrt n)$，其中$k$较小，且你的方法提前限制了$n$的上限，因此时间复杂度优于我不加处理的$O(n)$的代码
不过要是$n\le 10^7$就应该是我的方法快了，因为主要是因为你方法手动限制的上限才使得代码优于$O(n)$
还是要说一下，数据量到$10^7$的时候$O(n\log n)$的代码会有点危险(
by QWQ_HY_DFX @ 2024-02-21 22:13:21
@[zhu5001210249](/user/671246)
```java
package com.lianxi;
import java.util.Scanner;
public class P1217 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
if( a == 2) System.out.println(a);
if( a % 2 == 0 ) a++;
for (int i = a; i <= b; i+=2) {
int temp = i;
int result = 0;
int ans=huiWen(i);
if(ans==temp) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(temp) ; j++) {
if (temp % j == 0) {
flag = false;
break;
}
}
if(flag){
System.out.println(temp);
}
}
}
}
public static int huiWen(int i) {
int result=0;
while (i != 0) {
int ge = i % 10;
result = result * 10 + ge;
i /= 10;
}
return result;
}
}
```
抱歉啊不咋会java，应该是这样吧
by lunjiahao @ 2024-02-21 22:14:06
@[lunjiahao](/user/779970) 通过了，感谢呀大佬，我研究一下
by zhu5001210249 @ 2024-02-21 22:22:24