题目描述 Description
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;
输入输出格式 Input/output
输入格式:
第 1 行: 二个整数 a 和 b .
输出格式:
输出一个回文质数的列表,一行一个。
第 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: 找出所有的回文数再判断它们是不是质数(素数).
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 }
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
Ubíquelo a través del software del sistema “Find My Mobile” que viene con el teléfono o mediante un software de localización de números de teléfonos móviles de terceros.