求助!!!TLE四个点。。。Why?

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

jh2023 @ 2023-11-09 09:39:05

求助!!!TLE四个点。。。Why?

#include <bits/stdc++.h>
using namespace std;

bool prime(int a) {
    bool r = true;
    for (int i = 2; i <= a - 1; i++) {
        if (a % i == 0) {
            r = false;
            break;
        }
    }
    return r;
}

int main() {
    int a, b, number, nnn;
    string n, nn;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        number = i;
        nn = to_string(number);
        n = "";
        for (int j = to_string(number).length() - 1; j >= 0; j--) {
            n += to_string(number)[j];
        }
        nnn = stoi(n);
        if ((nnn == i) && prime(i)) {
            cout << i << '\n';
        }
    }
    return 0;
}

by jh2023 @ 2023-11-09 09:47:49

开了O2优化还是最后3个点TLE。


by jh2023 @ 2023-11-09 09:53:00

用printf和scanf也是一样。


by Kendieer @ 2023-11-09 13:09:05

求质数只需要i<=sqrt(a)就行,因为非质数必然存在一个大于等于sqrt(a)和一个小于等于sqrt(a)的数符合条件


|