今天下午看到这么一个题
找出 1 亿以内的回文质数
很自然的思路就是素数筛,然后验证回文性质
#include <iostream> #include <cmath> #include <ctime> #define TOTAL 100000000 using namespace std; bool is_prime[TOTAL]; void Sieve_of_Eratosthenes() { memset(is_prime, 1, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i=2; i<sqrt(TOTAL+0.5); i++) { if (is_prime[i]) { for (int j=i*i; j<TOTAL; j+=i) { is_prime[j] = false; } } } } void test_palin() { for (int i=2; i<TOTAL; i++) { if (is_prime[i]) { int cpy = i, sum; for (sum=0; cpy!=0; cpy/=10) { sum = sum*10 + cpy%10; } if (sum == i) { printf("%dn", i); } } } } int main() { Sieve_of_Eratosthenes(); test_palin(); printf("%lfn", (double)clock()/CLOCKS_PER_SEC); return 0; }
上面这个素数筛在我的电脑上跑需要 4.07 秒,加上验证函数,耗时在 5.0 秒左右波动
思路是没错,但是略慢了,可以看到主要时间耗在打表上,上网翻看了一下,http://wenku.baidu.com/view/8e…,别人的思路不是打表,而是先判断回文,再判断质数,而是质数判断就直接穷举去除,看到他的最好的方法方法四是 0.5 秒,于是照着这个思路,重新搞,简单分析可以知道,任何一个 k 位正整数都可以产生一个 2*k 位和一个 2*k-1 位两个回文整数,例如,12 可以产生 121 和 1221 这两个,然后我们又知道,1 亿以内最大的数就是 99999999 了,8 个 9,那产生的时候最大也就 4 位数就可以了,照着这个思路,得到如下代码
#include <stdio.h> #include <math.h> #include <time.h> int is_prime(int x) { for (int i=2; i<sqrt(x+0.5); i++) { if (x%i == 0) { return 0; } } return 1; } void gener_palin() { for (int i=1; i<10000; i++) { // 根据 k 位数 i 产生 2*k 位的回文数 int cpy = i, sum; for (sum=i; cpy!=0; cpy/=10) { sum = sum*10 + cpy%10; } if (is_prime(sum)) { printf("%dn", sum); } // 产生 2*k-1 位的回文数 cpy = i/10; for (sum=i; cpy!=0; cpy/=10) { sum = sum*10 + cpy%10; } if (is_prime(sum)) { printf("%dn", sum); } } } int main() { gener_palin(); printf("%lfn", (double)clock()/CLOCKS_PER_SEC); return 0; }
这个代码在我的机子上可以跑到 0.25 秒,如图
根据经验,卷屏输出是耗时大户,把 29 和 40 行注释掉,可以跑到 0.03 秒