• 周四. 4月 18th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签
python

洛谷-回文质数-过程函数与递归

由admin

11月 28, 2021
题目描述 Description
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。 
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;
 输入输出格式 Input/output
输入格式：
第 1 行: 二个整数 a 和 b .
输出格式：
输出一个回文质数的列表，一行一个。
 输入输出样例 Sample input/output
样例测试点#1
输入样例：
5 500
输出样例：

5
7
11
101
131
151
181
191
313
353
373
383

说明 description
Hint 1: Generate the palindromes and see if they are prime. 
提示 1: 找出所有的回文数再判断它们是不是质数（素数）. 

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below. 
提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。 

题目翻译来自NOCOW。
USACO Training Section 1.5

产生长度为5的回文数: 

1 for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
2      for (d2 = 0; d2 <= 9; d2++) {
3          for (d3 = 0; d3 <= 9; d3++) {
4            palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
5          }
6      }
7 }

思路：这题难度是有点大，范围竟然有一亿，太坑爹了！所以我对它做了些简化：

①从奇数开始找，每次i=i+2；

②没有偶数位的回文质数，省了一大把时间，真是造福人类啊！

③排除2、5的倍数

每个函数实现过程详解：

①判断回文数：存入一个数组，判断从前往后扫和从后往前扫是否一致。

②判断位数（检测长度是否大于一亿）：从前往后扫，返回循环次数就得了。

③判断质数（这个很重要哦）：i从3开始，每次i=i+2，再用那个数去试除i，如果刚好除尽，那么就是质数了，返回1。

代码①如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 int huiwen(int k);//判断回文数
 4 int hwlength(int k);//计算回文数的长度
 5 int prime(int k);//判断质数 
 6 int main()
 7 {
 8     int a,b,i,j;
 9     scanf("%d%d",&a,&b);
10     for (i=a;i<=b;i++)
11     {
12         if(i%2==0&&i!=2)//排除2的倍数
13             continue;
14         if(i%5==0&&i!=5)//排除5的倍数
15             continue;
16         if(hwlength(i)%2==0&&i!=11)//回文数的长度为偶且不为11
17             continue;
18         if(huiwen(i)!=1)//不是回文直接跳过
19             continue;
20         if(prime(i))//是质数 
21             printf("%d
",i);
22     }
23     return 0;
24 }
25 int huiwen(int k)  
26 {
27     int a[10],i=0,j;
28     while(k>0)//每一位存入数组，再判断 
29     {
30         a[i]=k%10;
31         k=k/10;
32         i++;
33     }
34     for (j=0;j<i;j++)//两重循环判断（前后后前扫法） 
35         if(a[j]!=a[i-j-1])//不是，返回0 
36             return 0;         
37     return 1;//结束后，是，返回1 
38 }
39 int hwlength(int k)  
40 {
41     int a[10],i=0;
42     while(k>0)
43     {
44         a[i]=k%10;
45         k/=10;
46         i++;
47     }
48     return (i);//循环了i次 
49 }
50 int prime(int k)  
51 {
52     int i;
53     for(i=3;i*i<=k;i=i+2)//这样可以减少好多次循环
54         if(k%i==0)
55         {
56             return 0;
57         }           
58     return 1;
59 }

 代码②如下（本C++代码为代码①的升级版，更快，更强，只是代码有点长(⊙o⊙)…）：

  1 #include<iostream>
  2 #include<cmath>
  3 #include<cstring>
  4 using namespace std;
  5 bool isprime(int a)
  6 {
  7     int i;
  8     for(i=3;i<=floor(sqrt(a)+0.5);i++)
  9         if(a%i==0)
 10             return false;
 11     return true;
 12 }
 13 int weishu(int a)
 14 {
 15     int i=0;
 16     while(a>0)
 17     {
 18         a/=10;
 19         i++;
 20     }
 21     return i;
 22 }
 23 int main()
 24 {
 25     int start,end,i1,i2,i3,i4,i5,hw,ws[2];
 26     cin>>start>>end;
 27     ws[0]=weishu(start);
 28     ws[1]=weishu(end);
 29     switch(ws[0])
 30     {
 31         case 1:
 32         {
 33             if(ws[1]<1)
 34                 break;
 35             for(i1=5;i1<=9;i1+=2)
 36             {
 37                    hw=i1;
 38                    if(hw>end)
 39                        break;
 40                    else if(hw>=start&&isprime(hw))
 41                        cout<<hw<<endl;
 42             }
 43         }
 44         case 2:
 45         {
 46             if(ws[1]<2)
 47                 break;
 48             if(end>=11&&start<=11)
 49                 cout<<"11"<<endl;
 50         }
 51         case 3:
 52         {
 53             if(ws[1]<3)
 54                 break;
 55             for(i1=1;i1<=9;i1+=2)
 56             {
 57                 for(i2=0;i2<=9;i2++) 
 58                 {
 59                        hw=100*i1+10*i2+i1;
 60                        if(hw>end)
 61                            break;
 62                        else if(hw>=start&&isprime(hw))
 63                            cout<<hw<<endl;
 64                 }
 65             }
 66         }
 67         case 4:
 68         {
 69             if(ws[1]<4)
 70                 break;
 71         }
 72         case 5:
 73         {
 74             if(ws[1]<5)
 75                 break;
 76             for(i1=1;i1<=9;i1+=2)
 77             {
 78                 for(i2=0;i2<=9;i2++) 
 79                 {
 80                     for(i3=0;i3<=9;i3++)
 81                     {
 82                            hw=10000*i1+1000*i2+100*i3+10*i2+i1;
 83                            if(hw>end)
 84                                break;
 85                            else if(hw>=start&&isprime(hw))
 86                                cout<<hw<<endl;
 87                        }
 88                 }
 89             }
 90         }
 91         case 6:
 92         {
 93             if(ws[1]<6)
 94                 break;
 95         }
 96         case 7:
 97         {
 98             if(ws[1]<7)
 99                 break;
100             for(i1=1;i1<=9;i1+=2)
101             {
102                 for(i2=0;i2<=9;i2++) 
103                 {
104                     for(i3=0;i3<=9;i3++)
105                     {
106                         for(i4=0;i4<=9;i4++)
107                         {
108                                hw=1000000*i1+100000*i2+10000*i3+1000*i4+100*i3+10*i2+i1;
109                                if(hw>end)
110                                    break;
111                                else if(hw>=start&&isprime(hw))
112                                    cout<<hw<<endl;
113                            }
114                     }
115                 }
116             }
117         }
118         case 8:
119         {
120             if(ws[1]<8)
121                 break;
122         }
123         case 9:
124         {
125             if(ws[1]<7)
126                 break;
127             for(i1=1;i1<=9;i1+=2)
128             {
129                 for(i2=0;i2<=9;i2++) 
130                 {
131                     for(i3=0;i3<=9;i3++)
132                     {
133                         for(i4=0;i4<=9;i4++)
134                         {
135                             for(i5=0;i5<=9;i5++)
136                             {
137                                    hw=100000000*i1+10000000*i2+1000000*i3+100000*i4+10000*i5+1000*i4+100*i3+10*i2+i1;
138                                    if(hw>end)
139                                        break;
140                                    else if(hw>=start&&isprime(hw))
141                                        cout<<hw<<endl;
142                                }
143                            }
144                     }
145                 }
146             }
147         }
148     }
149 }

admin

相关文章

python
对嵌入字符串中的数字进行排序
3月 7, 2023 [db:作者]
python
如何使用Pandas对excel文件中的数据进行排序。并对副本进行排序
3月 7, 2023 [db:作者]
python
在pygtk Treevi中添加新行
3月 7, 2023 [db:作者]
《洛谷-回文质数-过程函数与递归》有2个想法

  1. Wow, amazing blog structure! How long have you ever been blogging for?
    you make blogging glance easy. The total look of your website is great, let alone the content material!
    You can see similar here ecommerce

发表回复

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

You missed

python
python
python
python