请教!!66分

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

66QwQ99 @ 2023-12-02 21:01:50

#include <stdio.h>
#include <stdbool.h>

bool is_palindrome(int num) {
    int reversed = 0;
    int original = num;

    while (num > 0) {
        int digit = num % 10;
        reversed = reversed * 10 + digit;
        num /= 10;
    }

    return original == reversed;
}

int isprime(int i) {
    int ret = 1;
    int x;
    for (x = 2; x * x <= i; x++) {
        if (i % x == 0) {
            ret = 0;
            break;
        }
    }
    return ret;
}

int main() {
    int b, number, a;
    scanf("%d %d", &a, &b);
    int prime[b];
    int cnt = 0, cnt1 = 0;
    for (number = a; number <= b; number++) {
        if (isprime(number)) {
            prime[cnt++] = number;
        }
    }
    for (int n = 0; n < cnt ; n++) {
        if (is_palindrome(prime[n]))
            printf("%d \n", prime[n]);
    }
    return 0;
}

超时了,怎么办,哪里可以精简呢


by DustyMark @ 2023-12-02 21:13:46

@66QwQ99 az,你可以试试先搜出回文数,再判断他们是不是质数


by DustyMark @ 2023-12-02 21:16:49

@66QwQ99

for (number = a; number <= b; number++) {
        if (isprime(number)) {
            prime[cnt++] = number;
        }
    }
    for (int n = 0; n < cnt ; n++) {
        if (is_palindrome(prime[n]))
            printf("%d \n", prime[n]);
    }

可以直接改成

for (int i = a; i <= b; i++)
    {
        if(i>=1e7)break;
        if(hw(i) && zs(i))cout<<i<<"\n";
    }

注:hw就是判断回文,zs就是判断质数


by 66QwQ99 @ 2023-12-02 23:11:09

@Min6700 了解


by Kyrie2024 @ 2023-12-09 13:37:17

请问你过了吗,我也一直卡在66分?


|