大佬们帮忙看看,应该怎么优化,超时了

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

lhyLHY123456 @ 2024-10-18 23:25:20

#include <bits/stdc++.h>
using namespace std;
bool isprime(int n) {
    if (n <= 1) {
        return 0;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }return 1;
}
bool huiwen(int n) {
    string str = to_string(n);
    string re = string(str.rbegin(), str.rend());
    return str == re;
}
int main() {
    long long a, b;
    cin >> a >> b;
    for (long long i = a; i <= b; i++) {
        if (isprime(i) && huiwen(i)) {
            cout << i << endl;
        }
    }
    return 0;
}

by wIvy @ 2024-10-18 23:29:42

你可以试试预处理


by Yzmddsw @ 2024-10-18 23:32:40

@lhyLHY123456 其实如果先处理回文数再判质数是O(n)的,如果常数好或许可以卡过


by lhyLHY123456 @ 2024-10-18 23:37:52

@wIvy 谢谢谢谢


by lhyLHY123456 @ 2024-10-18 23:38:14

@Yzmddsw 谢谢大佬


|