求大佬救命!7 8 9TLE

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

wjf1023 @ 2023-01-14 11:43:10

#include <stdio.h>
int judgesu(int x)
{
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return 0;
    return 1;
}
int judgehuiwen(int x)
{
    int num = 0;
    int arr[10];
    if (x < 10)
        return 1;
    else {
        while (x!= 0) {
            arr[num] = x % 10;
            x /= 10;
            num++;
        }
        for (int i = 0; i < num/2; i++)
        {
            if (arr[i] != arr[num - 1 - i]) return 0;
        }
        return 1;
    }
}
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = a; i <= b; i++)
    {
        if (i % 2 != 0)
            if (judgesu(i))
                if (judgehuiwen(i))
                    printf("%d\n", i);
    }
    return 0;
}

by Elairin176 @ 2023-01-14 11:44:51

@wjf1023 先找回文数再找质数。


by Dr_Glitch @ 2023-01-14 11:46:43

你这里是用的试除法判断质数,对于这道题复杂度太高,可以换埃氏筛法或者线性筛来做


by SunLegend @ 2023-01-14 11:50:41

@wjf1023 判断方法没问题,但是可以证明100000000至1000000000之间没有回文素数,这样就不会t了

for (int i = a; i <=min(b,100000000); i++)

by wjf1023 @ 2023-01-14 13:54:14

@destructor 好嘞,谢谢大佬,我试一哈,新年快乐!


by wjf1023 @ 2023-01-14 13:54:43

@Dr_Glitch 好嘞,谢谢大佬,我去学习一下这两种方法,新年快乐!


by wjf1023 @ 2023-01-14 13:55:31

@huangyuhan123456 收到!谢谢大佬,我去改一下走一遍,新年快乐!


|