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/
