【算法】判断一个数是否是质数

一、质数的定义

质数（prime number）又称素数，有无限个。其定义为：
在大于1的自然数中，除了1和它本身以外不再有其他因数。

二、算法实现

1、基本判断思路：

在一般领域，对正整数n，如果用1到n-1的所有整数去除，均无法整除，则n为质数。C++代码如下

 //直观判断法，根据定义直接判断从2到n-1是否存在n的约数
bool isPrime_1(int num) {
	int temp = num - 1;
	for (int i = 2; i <= temp; i++) {
		if (num%i == 0)return 0;
	}
	return 1;
}

可见，该算法简单易懂，但是效率低下，时间复杂度为O(n)。

2、基本判断思路改进：

基于一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n) 的原理，我们可以对基本判断思路改进如下:
在一般领域，对正整数n，如果用2到√n 之间的所有整数去除，均无法整除，则n为质数。C++代码如下：

//直观判断法改进,一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)
bool isPrime_2(int num) {
	int temp = (int)sqrt(num);
	for (int i = 2; i <= temp; i++) {
		if (num%i == 0)return 0;
	}
	return 1;
}

可见，这种方法极大地改善了运行效率，时间复杂度为O(sqrt(n))。

3、素数两性定理判断思路

首先，我们先理解什么是孪生素数，孪生素数就是指相差2的素数对，例如3和5，5和7，11和13…。
那么什么是素数两性定理呢？

素数两性定理：
大于3的素数只分布在6n-1和6n+1两数列中。（n非0自然数）
相应的，6n-1数列中的合数叫阴性合数，其中的素数叫阴性素数；6n+1数列中的合数叫阳性合数，其中的素数叫阳性素数。

简单解释一下，令x≥1，我们将大于5的自然数作如下表示:
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
显然，6x、6x+2，6x+3，6x+4均不是素数，我们只需考虑6x-1和6x+1即可。换言之，我们在写算法的时候不需要一个一个的去累加循环判断每一个数是否可以整除，可以以6个数为一个循环步长，6x+4，只检查6x-1和6x+1。这样理论上，整体速度快了3倍。C++代码如下:

//素数两性定理判断法，大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；
bool isPrime_3(int num) {
	//2 3单独处理
	if (num == 2 || num == 3) return 1;
	//不在6的倍数两侧的一定不是质数
	if (num % 6 != 1 && num % 6 != 5) return 0;
	int temp = sqrt(num);
	//在6的倍数两侧的也可能不是质数
	for(int i=5;i<=temp;i+=6)
		if(num%i==0||num%(i+2)==0) return 0;
	//排除所有，剩余的是质数
	return 1;
}

可见，在5到sqrt(n)中每6个数只判断2个，整体速度理论上快了3倍，所以时间复杂度O(sqrt(n)/3)。