请问一下有三个测试点TLE是怎么回事？

P1217 [USACO1.5] 回文质数 Prime Palindromes

RyanStarrain @ 2023-09-17 22:18:00

#include <iostream>
using namespace std;
int a,b;
char c[10+2];
int ans;
bool Pali_Bool;
bool Prime_Bool;
bool Prime_Bool_Function(int Num)
{
    if (Num == 1)
    {
        return false;
    }
    for (int j = 2;j <= Num;j++)
    {
        if (Num%j == 0 && Num != j)
        {
            return true;    
        }
    }
    return false;
}
int main()
{
    cin >> a >> b;
    for (int i = a;i <= b;i++)
    {
        Pali_Bool = true;
        ans = 0;
        int i_num = i;
        while (i_num > 0)
        {
            ans++;
            c[ans] = (i_num % 10) + '0';
            i_num /= 10;
        }
        for (int i = 1;i <= ans;i++)
        {
            if (c[i] != c[ans + 1 - i])
            {
                Pali_Bool = false;
                break;
            }
        }
        if (Pali_Bool)
        {
            if (Prime_Bool_Function(i) == false)
            {
                cout << i << endl;
            }
        }
    }
    return 0;
}

by ZGSZ_AviationLover @ 2023-09-23 20:28:40

@RyanStarrain 不要暴力筛，O(\log n)，并且每一个n都要从2到n再重筛，建议欧拉/埃筛，O(n)并且判断回文可以这么写

bool is_par(int p){
    string str=to_string(p);
    string tmp=str;
    reverse(str.begin(),str.end());
    return tmp==str;
}

这样，if(is_par(i))就可以判断i是否为回文数，不需要枚举，STL多好

by ZGSZ_AviationLover @ 2023-09-23 20:34:59

埃氏筛部分代码

    isprime[0]=isprime[1]=false;
    for(int i=2;i*i<=maxn;i++){
        if(isprime[i]){
            for(int j=i*i;j<=maxn;j+=i){
                isprime[j]=false;
            }
        }
    }