66分 后三个TLE 求助

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

K_3_9_1 @ 2024-03-01 15:36:16

#include <iostream>
#include <cmath>
using namespace std;
bool IS_prim(int m)
{
    for (int i = 2; i <= sqrt(m); i++)
        if (m % i == 0)
            return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int a, b;
    bool flag = true;
    cin >> a >> b;
    if (a == 2)
        cout << 2 << "\n";
    if (b > 9999999)
        b = 9999999;
    if (a % 2 == 0)
        a++;
    for (int k = a; k <= b; k += 2)
    {
        if (IS_prim(k))
        {
            string str = to_string(k);
            if (k != 11 && str.size() % 2 == 0)
                continue;
            else
            {
                for (int i = 0, j = str.size() - 1; i < j; i++, j--)
                {
                    if (str[i] != str[j])
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    cout << k << "\n";
                flag = true;
            }
        }
    }
    return 0;
}

by fanjiayu666 @ 2024-03-01 16:26:49

只要枚举3,5,7位的回文质数就可以,5,7,11特判。可以证明,100000000以内的偶数位的回文数都是十一的倍数


|