11:回文素数
总时间限制:5000ms内存限制:65536kB
描述
一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数,
如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。
(注:不考虑超过整型数范围的情况)。
输入
位数n,其中1<=n<=9。
输出
第一行输出满足条件的素数个数。
第二行按照从小到大的顺序输出所有满足条件的素数,两个数之间用一个空格区分。
样例输入
1
样例输出
4
2 3 5 7
分析:参见百度百科
回文素数是一个既是素数又是回文数的整数。回文素数与记数系统的进位制有关。
回文素数是指,对一个整数n(n≥11)从左向右和从右向左读其结果值相同且是素数,即称n为回文素数。
除了11,偶数位的数不存在回文质数。4位,6位,8位……数不存在回文质数。
最初几个回文素数:11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929……两位回文素数1个,三位回文素数15个,五位回文素数93个,七位回文素数668个,九位回文素数5172个。
思路:
对n为偶数的情况,直接特殊处理。
对n为奇数的情况,可以先特殊处理n==1的情况,然后对n==3、5、7、9的情况按如下方法处理:
先想办法够造出一个n位的回文数temp然后判断temp是否是质数。
够造n位的回文数temp的方法:用所有的(n+1)/2位的数分别够造n位的回文数。例如:可以用123够造一个5位的回文数12321.
(注意:123可以够造出12321和32123两个回文数,但是我们只需要使用123够造12321,在接下来的循环过程中会使用321够造32123这个回文数。)
具体代码:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 int isPrime(int n);//判断n是否质数 5 long long huiWen(int n);//例如:n等于123,返回12321这样一个回文数 6 long myPow(int x);//计算并返回10^x 7 8 int main() 9 { 10 int n; 11 long begin,end,i; 12 long long a[8000]={0},count; 13 long long temp=0; 14 15 freopen("11.IN","r",stdin); 16 freopen("11.out","w",stdout); 17 18 scanf("%d",&n); 19 20 if(n==2) printf("1\n11\n"); 21 else if(n%2==0) printf("0\n"); 22 else if(n==1) printf("4\n2 3 5 7\n"); 23 else 24 { 25 n=(n+1)/2; 26 begin=myPow(n-1); 27 end=myPow(n); 28 count=0; 29 for(i=begin;i<end;i++) 30 { 31 temp=huiWen(i); 32 if(isPrime(temp)==1) { a[count]=temp; count++; } 33 } 34 printf("%d\n",count); 35 for(i=0;i<count;i++) 36 { 37 printf("%d ",a[i]); 38 } 39 } 40 return 0; 41 } 42 int isPrime(int n) 43 { 44 int x,i; 45 x=sqrt(n); 46 for(i=2;i<=x;i++) 47 { 48 if(n%i==0) return 0; 49 } 50 return 1; 51 } 52 long long huiWen(int n)//例如:n等于123,返回12321这样一个回文数 53 { 54 long long ans=n; 55 n=n/10; 56 while(n>0) 57 { 58 ans=ans*10+n%10; 59 n=n/10; 60 } 61 return ans; 62 } 63 long myPow(int x)//计算并返回10^x 64 { 65 int i; 66 long ans=1; 67 for(i=0;i<x;i++) ans=ans*10; 68 return ans; 69 }
题目连接:http://noi.openjudge.cn/ch0113/11/
今天的文章11:回文素数_前100个回文素数分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/47361.html