素数检测算法

前言

今天做ACM的时候，遇到了素数的检测，检测一个范围内的素数的时候，如果用最简单的那种方法，超时严重，因此学习了一个新的素数检测算法——素数筛选法，这里也是跟大家分享一下

素数

素数的定义

一个大于1的整数，如果不能被除1和它本身之外的其它正整数整除，则是素数（又称质数）

合数的定义

一个大于1的整数，如果不是素数则是合数。其中能整除这个数的正整数叫做约数，不等于1也不等于合数本身的约数叫做非平凡约数。

注意：

1既不是素数也不是合数

检测素数

所谓素数检测，就是给定任意一个大于1的整数，判断这个整数是否为素数。

因子检测法

方法：就是从2到ｎ-1一个个的拿来尝试，看能否整除ｎ，如果存在能够整数ｎ的（找到一个因子），则ｎ不是素数，否则认为ｎ是素数。实际，是不需要试探到ｎ-1的，只要的ｎ的二次方根即可，原因是：

设n = a * b,且a、b均为n非平凡约数，显然a > n的二次方根和b > n的二次方根不可能同时成立，因为同时成立时 a * b就会大于n，所以如果n存在非平凡约数，至少有一个小于等于n的二次方根，因此只要遍历到ｎ的二次方根即可。

因子检测的实现代码如下（ｃ）：

int isPrime(int n)
{
	int i, flag;
	flag = (n <= 1)? 0 : 1;
	
	for(i = 2; i <= sqrt(n); i ++)
	{
		if(n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}

测试结果：

时间复杂度：

很明显，因子检测算法的时间复杂度是0（ｎ的二次方根）,一般来说，这个时间复杂度已经很牛叉了，但是如果我要求ｎ以内所有的素数集合，那时间复杂度瞬间就到了n * n的二次方根，这个对于ｎ很大时是不可忍受的

素数筛选法

利用素数因子检测法去超找ｎ以内的所有素数，时间复杂度太高，不可忍受，因此这里介绍另外一种算法，素数筛选法，可以大大的节省时间，带来的直接功效是九度ａｃｍ关于素数检测的题我瞬间ａｃ，用素数因子检测基本都是ｗａ。

原理：

当i是素数的时候，则ｉ的所有倍数必然是合数。如果ｉ已经判断不是素数了，那么找到ｉ后面的质数来把这个质树的倍数筛掉。

求20以内素数的筛选过程：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

第一步，因为所有的偶数和0,1必然不是质数，则将这些数的对应的value标记为flase，其余为true。

第二步：

i = 3,由于prime[3] = 1,则prime[6],prime[9],prime[12],prime[15],prime[18]均标记为0;

i = 4,由于prime[4] = 0,则continue，不做处理;

i = 5 > sqrt(20),算法结束

时间复杂度：

这个时间复杂度由于我的数学知识有限，也没法把计算过程解释出来，总之确实是很快，至于为什么ｉ= 5就结束了，原因跟素数因子法里面的原理是一样的，因为ｎ的因子必然有一个是小于等于n的二次方根的。

素数筛选法实现代码：

void getPrimeArray(int *prime)
{
	int i, j;
	//初始化素数标识数组
	for(i = 0; i < max; i ++)
	{
		if((i == 2 || i % 2 != 0) && i != 1)
		{
			prime[i] = 1;
		} else
		{
			prime[i] = 0;
		}
	}
		
	//进行素数的筛选
	for(i = 2; i * i < max; i ++)
	{
		if(prime[i])
		{
			for(j = 2 * i; j < max; j += i)
			{
				prime[j] = 0;
			}
		}
	}

}

参考资料

张洋的博客——http://www.codinglabs.org/html/prime-test.html 我很崇拜的一个技术牛人