判断一个数是不是素数

1.素数的定义

素数又名质数，指除了 1 和本身外不再有其他因数的自然数。

特别规定 0 和 1 既不是质数也不是合数。最小的质数是 2，最小的合数是 4。

下面给出常见判断方法，效率依次提升，以 Golang 为例给出实现。

2.直接法

给定数 n（n>2），根据质数的定义，很容易想到遍历 [2,n-1] 看是否存在某个数可以整除它，如果存在则不是素数。

// isPrime 判断某个数是否是素数
func isPrime(n uint64) bool {
	if n <= 2 {
		return n == 2
	}
	for i := uint64(2); i < n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

这里特殊处理不大于 2 的数，因为遍历 [2,n-1] 需要 n>2。

算法时间复杂度为 O(n)，是最慢的实现。

3.初步优化

假如 n 是合数，必然存在非 1 的两个约数 p1 和 p2，其中p1<=sqrt(n)，p2>=sqrt(n)。由此我们可以改进上述方法优化循环次数。

func isPrime(n uint64) bool {
	if n <= 2 {
		return n == 2
	}
	sqrt := math.Sqrt(float64(n))
	for i := uint64(2); i <= uint64(sqrt); i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

算法时间复杂度为 O(sqrt(n))。

4.继续优化

继续分析，其实质数还有一个特点，除了 2 和 3，它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

上面的结论证明如下： （1）6x 能被 6 整除； （2）6x+2 能被 2 整除； （3）6x+3 能被 3 整除； （4）6x+4 能被 2 整除。 那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。

又因为合数有个性质，合数肯定有一个小于或等于根号的质因数，所以如果 n 能被 6 倍数两侧的数（才有可能是质数）整除，那么 n 是合数，否则 n 是素数。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数能否整除 n 即可。

func isPrime(n uint64) bool {
	if n < 5 {
		return n == 2 || n == 3
	}
	// 不在6的倍数两侧的一定不是质数
	if n%6 != 1 && n%6 != 5 {
		return false
	}
	sqrt := math.Sqrt(float64(n))
	for i := uint64(5); i <= uint64(sqrt); i += 6 {
		// 是否是合数
		if n%i == 0 || n%(i+2) == 0 {
			return false
		}
	}
	return true
}

算法时间复杂度为 O(sqrt(n)/6)。

5.Miller-Rabin 概率素性测试算法

尽管上面的 O(sqrt(n)/6) 的算法已经非常优秀了，但是面对更高数量级的“大数”却会显得力不从心，所以上面朴素简单的算法一般不会用于工程实践中，一般使用 Miller-Rabin 算法。

Miller-Rabin 的理论基础来源于费马小定理，利用随机化算法判断一个数是合数还是可能是素数。关于 Miller-Rabin 算法原理这里不详细展开。

Golang 标准库基于 Miller-Rabin 已经实现了素性判断的方法，下面看下如何使用。

对于小于 2^64 的数，可以使用 big.ProbablyPrime(0)，这种素性测试是100％准确的。

const n = 1212121
if big.NewInt(n).ProbablyPrime(0) {
    fmt.Println(n, "is prime")
} else {
    fmt.Println(n, "is not prime")
}

输出：

1212121 is prime

对于较大的数字，需要为 ProbablyPrime(n) 提供所需数量的测试 。对于 n 次测试，对于随机选择的非素数，返回 true 的概率最多为 (1/4)^n。一个常见的选择是使用 n = 20，这时误判概性率约为 0.000,000,000,001，基本可以认为是准确的了。

z := new(big.Int)
fmt.Sscan("170141183460469231731687303715884105727", z)
if z.ProbablyPrime(20) {
    fmt.Println(z, "is probably prime")
} else {
    fmt.Println(z, "is not prime")
}

输出：

170141183460469231731687303715884105727 is probably prime

其时间复杂度上界为 O(klog2​(n))，其中 k 为检测的轮数。增大 k 可以提高 Miller-Rabin 算法的准确度。

另外 Solovay–Strassen 也是工程中使用的概率素性判断算法，还有确定性算法 AKS，可在在多项式时间之内，决定一个给定整数是素数或者合数，感兴趣的同学可以了解一下这两个算法。

参考文献

[1] CSDN.判断一个数是不是质数(素数)，3种方式介绍 [2] 知乎.Go语言中检测一个数是否为素数