首页 > 代码库 > 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 素数回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。