11分菜狗,求大佬捞捞QAQ

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

ckx2333 @ 2023-10-07 20:44:52


#include<stdio.h>
int zhishu(int a) {
    if (a > 2) {
        for (int i = 3; i < a; ) {
            if (a % i == 0) {
                    a = 0;
                    break;
            }
            i+=2;
        }
        return a;
    }
}

int huiwen(int a) {
    //先判断几位数
    int i = 1;
    int b = a;
    int c = a;
    while (c >=10) {
        c /= 10;
        i++;
    }
//这个数有i位
    //放进数组
    int arr[9];

    for (int j = 0; j < i; j++) {
        arr[j] = b % 10;
        b /= 10;
    }
    if (i % 2 == 0) {
        for (int m = 0; m <= i / 2 && i - m - 1 >=0; m++) {
            if (arr[m] != arr[i - m - 1]) {
                a = 0;
                break;
            }
        }
    }
    else if (i % 2 != 0) {
        for (int m = 0; m <= (i - 1) / 2 && i - m - 1>=0; m++) {
            if (arr[m] != arr[i - m - 1]) {
                a = 0;

                break;
            }
        }
    }
    return a;
}
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int k;
    if (a < b && a >= 5 && b <= 10e8) {
        for (k = 5; k >= a && k <= b; k+=2) {
                if(huiwen(k)!=0&&zhishu(k)!=0{
                    printf("%d\n", k);
                }
        }
    }
    else {
        return 0;
    }
    return 0;
}

by 9gehetao @ 2023-10-07 20:57:10

TLE了吗


by 9gehetao @ 2023-10-07 20:59:21

可以试试打表(偷笑


by 9gehetao @ 2023-10-07 21:00:16

埃氏筛学了吗???


by chenlh0711 @ 2023-10-07 21:01:41

这样写素数超时,应该用埃拉筛啊

int zhishu(int a) {
    if(a==2||a==3){
        return 1;//这里要特判2、3
    }else{
        for(int i=0;i*i<a;i++){
            if(a%i==0){
                return 0;
            }
        }
    }
    return 1;
}

by 9gehetao @ 2023-10-07 21:02:50

@chenlh0711 Yes


by ckx2333 @ 2023-10-08 15:32:43

@9gehetao 最后一个TLE了(悲),但除了第一个和最后一个其他都是错的(悲悲)


by ckx2333 @ 2023-10-08 15:34:41

@9gehetao 。大一刚开始C的菜狗还没学到(悲),我马上滚去学,谢谢大佬提醒(鞠躬)


by ckx2333 @ 2023-10-08 15:36:16

@chenlh0711 搜嘎,这就是埃拉筛啊,谢谢大佬(鞠躬)


|