http://acm.hdu.edu.cn/showproblem.php?pid=2138

一开始感觉是水题，就直接点submit在页面上写

bool prime(int n)
{
	if(n < 2)
		return false;
	if(n == 2)
		return true;
	int m = sqrt((float)n);
	for(int i = 3; i <= m; i+=2)
		if(n%i == 0)
			return false;
	return true;
}

但是超时了。因为这样的时间复杂度很依赖n。但n>1000000000时需要几s才能判断出来。

换一种写法：

bool prime(int n)
{
	if(n < 2)
		return false;
	if(n == 2)
		return true;
	if(n % 2 == 0)
		return false;
	int d = 3;
	int l = n;
	while(l > d)
	{
		if(l % d == 0)
			return false;
		l = l / d;
		d += 2;
	}
	return true;
}
AC了。先排除偶数，剩下的合数必然含有奇数因子 3，5，7。。。

作者: Bourbon 发表于 2011-07-09 10:52 原文链接

关键字 how many prime numbers,解题报告,一种比较高效的素数判断算法
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架