这个程序是哈尔滨工业大学的一道作业题,有一位朋友昨晚让我看了这道题目,我发现这道题目还真不是那么简单。学校对刚刚学完数组的大一同学出此题目是否欠妥呢?
现在先看看题目。
1.Prime Palindromes
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
PROGRAM NAME: pprime
INPUT FORMAT
Line 1: Two integers, a and b
SAMPLE INPUT (file pprime.in)
5 500
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.
SAMPLE OUTPUT (file pprime.out)
5
7
11
101
131
151
181
191
313
353
373
383
这道题目表面上来看比较简单,因为是很基础的算法——求素数和回文数。我先写了一个用循环求余法求素数和检验是否回文的函数,循环查找符合条件的数。
结果不出所料,显然超时。我需要对它进行优化。
所谓优化,无非是三点思路:减少判断是否素数的时间;减少判断是否回文的时间;减少被选数的数量,提高数的精确性。
判断回文并没有什么好优化的地方。就是把前后对称的每位对比一下,防止重复对比即可。
那么判断素数呢?
首先,我们考虑是否可以用筛法求素数。筛法求素数是先把所有的数保存在一起,然后去掉不符合要求的数。每次他找到一个素数,就把这个素数的所有倍数均删除,最后留下的就是需要的素数。
但是这种算法在本题是行不通的,因为数据范围高达 1,000,000,000,如果我们使用筛法,占用内存太大,然而这道题目要求的内存不超过 32MB。
所以我们继续优化求余法。首先,所有的偶数都可以排除(除2以外);其次,所有偶数位的数都可以排除。因为这样的数的奇数位和偶数位之和可以被11整除,这样的数一定可以被11整除,因此不可能是素数;另外,开头是0、2、4、5、6、8的可以排除,因为这样的回文数一定不是素数。
最后,还可以使用筛法的思路优化素数算法。因为要检查所有的数,对于大数的运算量过大;考虑下面的想法:如果一个数不能整除比他小的所有的素数,那么他一定是素数。原因是一个合数总能被分解为好多素数的积;如果每个质数都不能整除,那么也肯定不会有合数可以整除。
基于上述思路,再结合在求余法中广为应用的优化:只需要判断sqrt(该数)之前是否可以被整除,我们就可以确定,对于小于等于1,000,000,000 的数,只需要保存 10000 之前的素数,然后使用这些质数就可以校验所有的数是否是素数。
那么如何减少数的范围呢?根据偶数位的数一定不成立、开头结尾不能是0、2、4、5、6、8的要求,可以不穷举所有数,直接使用循环生成回文数表。而且,只需要循环数的一半,就可以生成对应的回文数表。
所以最后,我用的算法是这样的:先直接算出10000内的质数表,生成所有小于取值范围并且剪枝过的回文数表,并用质数表去验证是否为质数。
程序如下(最长用时 0.02 秒)
/* ID:cxj6661 PROG:pprime LANG:C++ */ /* * Prime Palindromes * By Ceeji * Type: Normal * For: Friend(Liuhaodong) * Date: 2010-10-30 * Under CC 3.0 */ #include <iostream> #include <cmath> #include <string> #include <fstream> #include <cstring> using namespace std; const int maxl = 10, maxp = 10000; const char *inf_name = "pprime.in"; const char *ouf_name = "pprime.out"; int primes[maxp]; bool isp[maxp]; int plen; bool prime(int i) { if (i == 1) return false; if (i == 2 || i == 3) return true; if (i % 2 == 0) return false; int m = (int)sqrt((float)i); if (m > i - 1) m = i - 1; for (int j = 3; j < m + 1; j += 2) { if (i % j == 0) return false; } return true; } bool prime2(int i) { if (i < 10001) { return isp[i]; } if (i == 2 || i == 3) return true; if (i % 2 == 0) return false; int m = (int)sqrt((float)i); for (int j = 0; j < plen; ++j) { if(primes[j] > m + 1) break; if (i % primes[j] == 0) return false; } return true; } bool palindrome(int i) { char ch[10]; sprintf(ch, "%d", i); int l = strlen(ch); for (int p = 0; p < l / 2 + 1; ++p) { if (ch[p] != ch[l - p - 1]) return false; } return true; } int main(void) { ifstream fin(inf_name); ofstream fou(ouf_name); int a, b; fin >> a >> b; /* Find primes which are not bigger than 10000; this will accelerate the prime2 function to check number from 0 to 1,000,000,000. */ for (int i = 1; i <= 10000; ++i) { if (prime(i)) { primes[plen++] = i; isp[i] = true; } else isp[i] = false; } for (int i = a; i < 100; ++i) { if (i >= a && i <= b && palindrome(i) && prime2(i)) { fou << i << endl; } } int now = 0; /* Now check for the palindrome with width of 3 */ for (int i = 1; i < 10; i += 2) for (int j = 0; j < 10; ++j) { if (i == 5) continue; now = i * 100 + j * 10 + i; if (now < a) continue; if (now > b) { fou << flush; return 0; } if (prime2(now)) fou << now << endl; } /* Now check for the palindrome with width of 5 */ for (int i = 1; i < 10; i += 2) { if (i == 5) continue; for (int j = 0; j < 10; ++j) for (int k = 0; k < 10; ++k) { now = i * 10000 + j * 1000 + k * 100 + j * 10 + i; if (now < a) continue; if (now > b) { fou << flush; return 0; } if (prime2(now)) fou << now << endl; } } /* Now check for the palindrome with width of 7 */ for (int i = 1; i < 10; i += 2) { if (i == 5) continue; for (int j = 0; j < 10; ++j) for (int k = 0; k < 10; ++k) for (int l = 0; l < 10; ++l) { now = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i; if (now < a) continue; if (now > b) { fou << flush; return 0; } if (prime2(now)) fou << now << endl; } } /* Now check for the palindrome with width of 9 */ for (int i = 1; i < 10; i += 2) { if (i == 5) continue; for (int j = 0; j < 10; ++j) for (int k = 0; k < 10; ++k) for (int l = 0; l < 10; ++l) for (int m = 0; m < 10; ++m) { now = i * 100000000 + j * 10000000 + k * 1000000 + l * 100000 + m * 10000 + l * 1000 + k * 100 + j * 10 + i; if (now < a) continue; if (now > b) { fou << flush; return 0; } if (prime2(now)) fou << now << endl; } } fou << flush; return 0; } |
估计是想让学生打表用数组存吧,哈哈
果断表示打表er无压力……
@Koala.Guan:我就是用打表法来做的,用筛选法打表,没超空间,但是超时了!!!
line93: Find primes which are...
@daniel:tks