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

题目描述 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 }