新手求助，后3个TLE

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

Lalala1a @ 2024-07-11 20:04:20

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
bool zhishu(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)return false;
    }
    return true;
}

int main()
{
    int a, b;
    cin >> a >> b;
        for (int i = a; i <= b; i++)//判断回文数 101 1001 12021 0 length-1 1 length-2
        {
            if (i == 2 || i % 2 != 0)
            {
                if (i < 10&& zhishu(i))
                {
                    cout << i << endl;
                    continue;
                }
                if(i==11)
                {
                    cout << 11 << endl;
                    continue;
                }
                if (i>11&&i % 11 != 0&&to_string(i).length()%2!=0)
                {
                    bool flag = true;
                    for (int j = 0; j <= (to_string(i).length() / 2) - 1; j++)
                    {
                        if (to_string(i)[j] != to_string(i)[to_string(i).length() - j - 1])flag = false;
                    }
                    if (flag == true && zhishu(i))cout << i << endl;
                }
            }
        }

}

新手求助，后3个TLE

by Lalala1a @ 2024-07-11 20:05:18

注释是在想判断回文数的时候随便找个地方写的，别在意。

by Starmoon_dhw @ 2024-07-11 20:13:58

思路问题，你的方法是直接在[a,b]范围内暴力枚举，按照数据范围，a如果是5，b如果是一亿，你的程序就一定会TLE了

我建议你考虑构造，倒着来考虑这个问题，毕竟构造的话，每位是0~9 10个数，因为是回文数，所以最多一亿时也只要5重循环10^5肯定不超时

另外，以后求字符串长度的函数不要放在循环中，因为求字符串长度的函数也是走一遍字符串计算的，这样子你的时间复杂度也会变多(这题关系不大)

by w2z2j2 @ 2024-07-11 20:14:24

其实在循环a到b判断的时候就已经有问题了，可参考一下题目最后的回文数生成。也就是说可以生成回文数使这个回文数>a并且<b,在判断它是否是质数，这样复杂度就大大降低了

by wangqiyu_why @ 2024-07-13 14:28:56

循环可以改成i+=2，因为题目说5<a，可以改成if嵌套,先判断回文，在判断质数

if (flag)
{
    if(zhishu(i)
    {
        cout<<i<<endl;
    }
}

by wangqiyu_why @ 2024-07-13 14:30:30

如果发现不是回文，可以直接break

if (to_string(i)[j] != to_string(i)[to_string(i).length() - j - 1])
{
    flag = false;break;
}

by ETO_NOI @ 2024-07-16 18:40:00

数位是八位的数才不可能是回文质数，因为一定会有十一这个因数

|