88,最后一个超时了

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

13813675795hzq @ 2023-02-26 09:45:08

#include <iostream>
#include <string>
using namespace std;

int a1(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0) return 0;
    }
    return 1;
}
int a2(string x)
{
    for (int i = 0; i <= (x.size() - 1) / 2; i++)
    {
        if (x[i] != x[x.size() - 1 - i]) return 0;
    }
    return 1;
}

int main()
{
    int b, e;
    cin >> b >> e;
    for (int i = b; i <= e; i++)
    {
        int t = i;
        string s = "";
        while (t != 0) {s += t % 10 + '0'; t /= 10;}
        if (a2(s) && a1(i)) cout << i << "\n";

    }

    return 0;
}

by Ruiqun2009 @ 2023-02-26 09:50:02

@13813675795hzq e 上限为 9989899


by InversionShadow @ 2023-02-26 10:05:39

@13813675795hzq 所以 i <= min(e, 9989899);


by 13813675795hzq @ 2023-02-26 17:58:07

谢谢,这作者没让我查质数表啊


by Jenosa @ 2023-03-07 16:26:14

@13813675795hzq 没有优化质数求解是3个超时,优化后是1一个 但是最后一个超时还有更好的优化方案吗?


|