第一次三个超时,第二次尝试只生成回文数,结果还不如第一次了。请问怎么优化啊?
查看原帖
第一次三个超时,第二次尝试只生成回文数,结果还不如第一次了。请问怎么优化啊?
914883
shy2757539057楼主2023/7/13 12:15
第一次的
#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;
}
2023/7/13 12:15
加载中...