11:回文素数_前100个回文素数

11:回文素数_前100个回文素数11:回文素数总时间限制:5000ms内存限制:65536kB描述 一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数, 如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。 (注:不考虑超过整型数范围的情况)。输入 位数n,其中1<=

11:回文素数_前100个回文素数"

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

(0)
编程小号编程小号
上一篇 2023-09-04
下一篇 2023-09-04

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注