求大佬看看TLE了最后一个点，我是先筛质数再判断回文超，最后时了

ljx_gkx @ 2023-03-26 17:22:46

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e8+10;
int a, b;
int primes[N];  //质数的数组！ 
bool st[N];
int cnt;

void is_prime(int n)
{
    for (int i=2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j=0; primes[j]*i <= n; j ++)
        {
            st[primes[j]*i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

bool huiwen (int nums)
{
    string str = to_string(nums);
    int l=0, r=str.size()-1;
    while (l < r)
    {
        if (str[l++] != str[r--])
            return false;
    }

    return true;
}

int main()
{
    cin >> a >> b;
    is_prime(b);    

    for (int i=0; i < cnt; i ++)
    {
        if (primes[i] >= a && primes[i] <= b)
            if (huiwen(primes[i]))
                cout << primes[i] << endl;
    }
    return 0;
}

by Aisaka_Taiga @ 2023-03-26 17:24:50

判断回文的时候偶数肯定不是回文质数吧，你i+=2试试能不能卡过去

by ljx_gkx @ 2023-03-26 17:33:09

@Aisaka_Taiga 还是不能

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e8+10;
int a, b;
int primes[N];  //质数的数组！ 
bool st[N];
int cnt;

void is_prime(int n)
{
    for (int i=2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j=0; primes[j]*i <= n; j ++)
        {
            st[primes[j]*i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

bool huiwen (string str)
{   
    int l=0, r=str.size()-1;
    while (l < r)
    {
        if (str[l++] != str[r--])
            return false;
    }

    return true;
}

int main()
{
    cin >> a >> b;
    is_prime(b);    

    for (int i=0; i < cnt; i ++)
    {
        if (primes[i] >= a && primes[i] <= b)
        {
            int t = primes[i];
            string str = to_string (t);
            if (str.size()%2!=0 || primes[i]==11)
                if (huiwen(str))
                    cout << primes[i] << endl;
        }
    }
    return 0;
}

by Maysoul @ 2023-03-26 17:37:57

@ljx52lm 你这在条件里改当然不能降复杂度了，直接在函数本身里判断才行

by ljx_gkx @ 2023-03-26 18:34:10

@Maysoul 啊这，我没有听懂大佬，不过上面那位大佬说的i+=2 我估计是不行了的，因为我存的是质数，枚举的时候枚举的是质数，i是质数数组的下标。

by ljx_gkx @ 2023-03-26 18:34:49

@Aisaka_Taiga i+=2 我估计是不行了的，因为我存的是质数，枚举的时候枚举的是质数，i是质数数组的下标。

by __JiCanDuck__ @ 2023-03-26 18:39:13

卡常把

by Aisaka_Taiga @ 2023-03-26 18:53:29

@ljx52lm 你或者可以换个思路比如先找回文数在判质数（？

by cyyy0408 @ 2023-03-26 23:34:55

bool zhishu(int n){ 
    if(n<2){
        return false; 
   } 
   for(int i=2;i*i<=n;i++){ 
        if(n%i==0){
            return false; 
        } 
    }
    return true; 
} 

by cyyy0408 @ 2023-03-26 23:58:11

分享个一重循环的判断质数，用不到数组之类的，你试试

还有就是huiwen函数耗时还是太长了

ps:正常的huiwen函数这题不行，建议看看题目的提示

写不出来可以找我要huiwen代码awa

by cyyy0408 @ 2023-03-27 00:06:12

写不出来再看哦~ 耗时最多的一个点用了10ms

#include<iostream>
#include<cmath>
using namespace std;
const int n=100000;
int hw[n]={2,3,5,7,11},r[n],t=5;

void build(){
    for(int d1=1;d1<=9;d1+=2){
        for(int d2=0;d2<=9;d2++){
            hw[t++]=100*d1+10*d2+d1;
        }
    }
    for(int d1=1;d1<=9;d1+=2){
        for(int d2=0;d2<=9;d2++){
            for(int d3=0;d3<=9;d3++){
                hw[t++]=10000*d1+1000*d2+100*d3+10*d2+d1;
            }
        }
    }
    for(int d1=1;d1<=9;d1+=2){
        for(int d2=0;d2<=9;d2++){
            for(int d3=0;d3<=9;d3++){
                for(int d4=0;d4<=9;d4++){
                    hw[t++]=1000000*d1+100000*d2+10000*d3+1000*d4+100*d3+10*d2+d1;
                }
            }
        }
    }
}//建立回文数组
bool zhishu(int n){
    if(n<2){
        return false;
    }
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}//判断质数
int main(){
    int a,b;
    cin>>a>>b;
    build();
    for(int i=0;i<t;i++){
        if(hw[i]>=a&&hw[i]<=b){
            if(zhishu(hw[i])){
                cout<<hw[i]<<endl;
            }
        }
    }
    return 0;
}