第一次三个超时,第二次尝试只生成回文数,结果还不如第一次了。请问怎么优化啊?

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

shy2757539057 @ 2023-07-13 12:15:32

第一次的
#include <iostream>
#include <cmath>
using namespace std;

int main(void)
{
    bool judge=0;
    int a,b;//范围
    int reverse=0;//倒过来的数
    int x=1;//个各位上的数
    int y=0;//多少位
    scanf("%d %d",&a,&b);
    for(int i=a;i<=b;i++){
        for(int j=1;x!=0;j++){//判断有几位数
            x=(int)(i/pow(10,j));
            y++;
        }
        for(int j=0;j<y;j++){//将数反过来,要用到是几位数y
            x=i/(int)(pow(10,j))%10;
            if(x!=i/(int)(pow(10,y-j-1))%10)break;
            reverse+=(int)(x*pow(10,y-j-1));
        }
        if(reverse==i){//若是回文数,判断是不是质数
            judge=1;//是回文数通过
            for(int k=2;k<i;k++){
                if(i%k==0){
                    judge=0;//不是质数不通过
                    break;
                }
            }
        }
        y=0;//初始化
        x=1;
        reverse=0;//初始化
        if(!judge)continue;//不通过就继续循环,通过就打印
        printf("%d\n",i);
        judge=0;
    }

    return 0;
}
第二次的
#include <iostream>
#include <cmath>
using namespace std;

int main(void)
{
    int num = 4;
    bool judge = 1;
    int a, b;
    int x = 1,e = 0;
    scanf("%d %d", &a, &b);
    int e3 = 9, e5 = 9, e7 = 9;
    x = 1;
    for (int j = 1; x != 0; j++)
    { // 判断b有几位数
        x = (int)(b / pow(10, j));
        e++;
    }
    switch (e)//减小运算区间
    {
        case 9:
        break;
    case 8:
        e7 = (int)(b / pow(10, 7));
        break;
    case 7:
        e7 = (int)(b / pow(10, 6));
        break;
    case 6:
        e5 = (int)(b / pow(10, 5));
        e7 = 0;
        break;
    case 5:
        e5 = (int)(b / pow(10, 4));
        e7 = 0;
        break;
    case 4:
        e3 = (int)(b / pow(10, 3));
        e5 = 0;
        e7 = 0;
        break;
    case 3:
        e3 = (int)(b / pow(10, 2));
        e5 = 0;
        e7 = 0;
        break;
    default:
    e3=0;e5=0;e7=0;
        break;
    }
//仅生成回文数
    for (int i = 0; i <= e7; i++)         // 7
        for (int j = 0; j <= e5; j++)     // 5
            for (int k = 0; k <= e3; k++) // 3
                for (int g = 0; g <= 9; g++)
                { // 1
                    if (i != 0)
                        num = i + j * 10 + k * 100 + g * 1000 + k * 10000 + j * 100000 + i * 1000000;
                    if (j != 0 && i == 0)
                        num = j + k * 10 + g * 100 + k * 1000 + j * 10000;
                    if (k != 0 && i == 0 && j == 0)
                        num = k + g * 10 + k * 100;
                    if (i == 0 && j == 0 && k == 0 && g >2)//把11加进去
                        num = g+2;
                    for (int a = 2; a < num; a++)
                    {
                        if (num % a == 0)
                        {
                            judge = 0; // 不是质数不通过
                            break;
                        }
                    }
                    if (judge && num >= a && num <= b)
                        printf("%d\n", num);
                    judge = 1;
                }

    return 0;
}

by Michaellg @ 2023-07-13 12:35:47

@shy2757539057 判断质数时只需要试到 \sqrt{n}

判断质数的代码:

bool isprime(int n) {
    if(n == 1 || n == 0)
        return false;
    for (int i = 2; i*i <= n; i++)
        if (!(n%i))
            return false;
    return true;
}

by Michaellg @ 2023-07-13 12:56:52

b 有 4、6、8 位时 e3 e5 e7 应赋值为 9,而不是 b 的最高位。


by Michaellg @ 2023-07-13 13:01:49

经测试,这些改完后就可以 AC。


by shy2757539057 @ 2023-07-13 14:50:13

@Michaellg 谢谢! (o゜▽゜)o❀


|