最后仨一直tle,,再考虑要不要打表(T_T)

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

du_jiao @ 2023-03-16 15:23:32

#include<stdio.h>
int i=0;        //全局变量i
int a,b;
int c=0;        //记录回文数个数
void zhishu(){  //判断是否为质数并输出值
    int l=0;
    if(i%2==0)
        l=1;
    if(i%2!=0)
        for(int j=3;j<i;j+=2)
            if(i%j==0)
                {l=1;break; }
    if(l==0)
        {printf("%d,",i);c++;}
}
void huiwen(){  //判断回文数
    int  x=0,a=i;
    for(;a>0;){
        x=a%10+x*10;
        a=a/10;
    }
    if(x==i)
        zhishu();
}
int main (){
scanf("%d%d",&a,&b);
if(b%2==0)
    b--;
/*
for(int k=a;k<=b;k++){
    if(k%2==0)
            continue;
    if(k==12) k+=88;
    if(k==1000) k*=10;
    if(k==100000) k*=10;
    if(k==9989899) {
            i=k;
            zhishu();
            break;
    }
    i=k;
    huiwen();
}
*/
for(i=a;i<=b;i++){
    if(i%2==0)
        continue;
    if(i==12) i+=88;
    if(i==1000) i*=10;
    if(i==100000) i*=10;
    if(i==9989899)
        {zhishu();break;}
    huiwen();
}
printf("\n\n%d",c); //输出回文数个数
return 0;
}

by du_jiao @ 2023-03-16 15:32:31

是不是一共有779个回文数字/(ㄒoㄒ)/~~


by sidekick257 @ 2023-03-16 16:15:37

你为什么要判断回文数


by du_jiao @ 2023-03-16 16:22:01

捂脸.jpg 我注释没写清楚,,,判断 i 是否为回文数


by sidekick257 @ 2023-03-16 16:23:18

@du_jiao 难道不是1e4生成回文数然后判质数吗,你1e9跑回文数当然会炸啊


by sidekick257 @ 2023-03-16 16:24:23

哦,是1e3和1e8


by sidekick257 @ 2023-03-16 16:25:39

你跑回文数前几位后面几位就是确定的然后判质数,不要先判回文数再判质数


by du_jiao @ 2023-03-16 16:32:28

我一会试试,,刚看到1e4,1e9愣住了(没听老师提过这些东西) 裂开


by sidekick257 @ 2023-03-16 16:36:41

@du_jiao 就是10^410^9


by du_jiao @ 2023-03-16 16:51:59

也就是说,是不是可以用外循环确定回文数字的相同部分,内循环确定中间数值(即确定具体回文数字),最后再判定下素数并输出就行了,,头大,梦回高中,,膜拜.JPG


|