1亿以内的回文质数

今天下午看到这么一个题

找出 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 秒

Leave a Reply

Your email address will not be published. Required fields are marked *