首页 > 代码库 > 素数回文

素数回文

2024-08-01 03:50:32   211人阅读

Problem Description
xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);
 
Input
这里有许多组数据，每组包括两组数据a跟b。
 
Output
对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。
 
Sample Input
5 500
 
Sample Output
5
7
11
101
131
151
181
191
313
353
373
383
 
分析：除了11外，任意偶数长度的回文都不是素数因为都会被11整除。题目给的范围里最大的回文素数就是9999999。所以数组只要开到这个数就够了，减少了很多数的筛选与数组的空间。
 
 1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4  5 #define N 10000000   //9999999是题目要求范围的最大回文数 6 char flag[N]; 7  8 int palindrome_number(int number); 9 10 int main(){11     int i;12     int j;13     int a;14     int b;15 16     memset(flag,‘0‘,N);17     flag[0]=‘1‘;18     flag[1]=‘1‘;19 20     for(i=2;i<=sqrt((double)N);i++){21         if(flag[i]==‘0‘){22             for(j=i*i;j<=N;j+=i)23                 flag[j]=‘1‘;24         }25     }26 27     while(scanf("%d%d",&a,&b)!=EOF){28         for(i=a;i<=b;i++){29             if(i>N-1)30                 continue;31 32             if(palindrome_number(i)==1 && flag[i]==‘0‘)33                 printf("%d\n",i);34         }35 36         printf("\n");37     }38 39     return 0;40 }41 42 int palindrome_number(int number){43     int array[9];44     int i;45     int length;46     int flag;47 48     i=0;49     while(number){50         array[i]=number%10;51         i++;52         number/=10;    53     }54     length=i;55 56     flag=0;57     for(i=0;i<length/2;i++){58         if(array[i]!=array[length-i-1]){59             flag=1;60             break;61         }62     }63 64     if(flag==1)65         return 0;66 67     else68         return 1;69 }

 

素数回文


联系
我们