66分，3TLE，为啥超时，跪求大佬帮助

XDYZ_N @ 2024-02-21 21:35:09

#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){
    int a=m,w=0;
    for(int i=2;i<=a-1;i++){
        if(a%i==0){
            return 0;
            break;
        }
        else w++;
    }
    if(w == a-2) return 1;
}
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i = a;i<=b;i++)
    {
        if(qw(i) == 1)
        {
            if(as(i) == 1)
            {
                cout<<i<<endl;
            }
        }
    }
    return 0;
}

by lunjiahao @ 2024-02-21 21:40:02

@XDYZ_N

每一个数都枚举的话复杂度逼近甚至超过 O(10^8) ，有一部分的数据会超时

by lunjiahao @ 2024-02-21 21:42:01

一个回文数的位数为偶数不为质数（除11以外）

by lunjiahao @ 2024-02-21 21:52:27

ACcode:

#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:55:02

时间复杂度约为 O(n\log n)，其中 n 最大为 5\times10^6

by zhu5001210249 @ 2024-02-21 21:59:08

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 22:00:02

@lunjiahao 大佬看看

by QWQ_HY_DFX @ 2024-02-21 22:01:48

首先，你判素数的函数是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

by QWQ_HY_DFX @ 2024-02-21 22:13:21

@lunjiahao

理论最坏时间复杂度为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 lunjiahao @ 2024-02-21 22:14:06

@zhu5001210249

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 zhu5001210249 @ 2024-02-21 22:22:24

@lunjiahao 通过了，感谢呀大佬，我研究一下