首页 > 代码库 > hdu-1431 素数回文

hdu-1431 素数回文

 题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1431

题目类型:

暴力打表、DFS

题意概括:

找出一个区间内所有的素数回文

解题思路:

暴力打表:我通过打表判断出[5,100000000]中素数个数<回文个数,并且判断出最大的素数回文是9989899,所以只需打表判断5-9989900之间所有的素数回文,判断的时候先判断素数,在判断是否是回文,然后在判断输入的相应输出,当时还不会筛选法求素数。耗时936MS。

DFS:通过位数创造8位数以内的所有回文,sort之后输入判断输出,耗时38MS,因为时间太长了,代码丢失了,也懒得写了。

题目:

素数回文

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19512    Accepted Submission(s): 4606


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
 

 

Author
xiaoou333

 

# include <stdio.h># include <math.h>int Prime(int x);int Palindrome_number (int x);int c[20000];int main (){    int a,b,i,z=0;    for(i=5;i<=9989900;i++)    {        if(Palindrome_number(i)==1)        {            c[z]=i;            z++;        }    }    while(scanf("%d%d",&a,&b)!=EOF)    {        if(b>=9989900)        b=9989900;        for(i=0;i<=z;i++)        {            if((c[i]>=a)&&c[i]<=b)            printf("%d\n",c[i]);        }        printf("\n");    }}int Prime(int x){    int i,k;    if(i==1)    return 0;    for(i=2;i<=(int)sqrt(x);i++)    {        if(x%i==0)        return 0;    }    return 1;}int Palindrome_number(int x){    int i,y,l,a[100];    y=x;    if((x<10)&&(Prime(x)==1))    return 1;    l=(int)log10(x)+1;    for(i=0;i<l/2;i++)    {        a[i]=x%10;        x/=10;    }    for(i=l/2;i<l;i++)    {        a[i]=x%10;        x/=10;        if(a[i]!=a[l-i-1])        return 0;    }    if(Prime(y)==1)    return 1;}

 

hdu-1431 素数回文