质数是除了 1 和它本身，没有其他因数的自然数，根据其定义，很容易想到对于数字 N (N >= 2) 通过遍历，判断 2 ~ N - 1 之间的数能否整除 N ，能则不是，否则是：
func isPrime(n int) bool { | |
if n < 2 { | |
return false | |
} | |
for i := 2; i < n; i++ { | |
if n%i == 0 { | |
return false | |
} | |
} | |
return true | |
} |
但这也容易想到，其效率不高，要挨个判断过去。实际上，不必把 2 ~ N - 1 之间的数都判断了，只需要 `2 ~ sqrt (N)`` 之间的数判断就行。
容易想到，对于 i = sqrt (N) 来说，i * i = N, 其所有可能的因子已经被检查过了。再大将超过范围，或者说其因子中，较小的一个一定包含在 2 ~ i 之间了。
于是可以修改成这样：
func isPrime(n int) bool { | |
if n < 2 { | |
return false | |
} | |
//i <= n/i 与 i * i <= n 等价，也相当于 i <= math.Sqrt (n) | |
for i := 2; i <= n/i; i++ { | |
if n%i == 0 { | |
return false | |
} | |
} | |
return true | |
} |
质数是不能被其他任何数整除的自然数。所有大于 3 的质数可以表示为 6k ± 1 的形式（即在 6 的倍数的两侧）。这是因为一个数如果不是 6 的倍数，它要么落在 6k ± 1 的位置，要么它就不是质数（它能被 2 或 3 整除）。
例如，考虑以下数：
- 6 * 1 = 6
- 6 * 1 - 1 = 5（质数）
- 6 * 1 + 1 = 7（质数）
更进一步的解释：所有整数可以表示为以下形式之一：6k、6k + 1、6k + 2、6k + 3、6k + 4、6k + 5。
- 6k，6k + 2，6k + 4 是偶数，不可能是质数（除非等于 2）。
- 6k + 3 是 3 的倍数，不可能是质数（除非等于 3）。
因此，剩下的可能质数形式只有 6k + 1 和 6k + 5（即 6k - 1）。
基于上面的原理，我们可以进一步优化判断：
func isPrime(n int) bool { | |
if n < 4 { | |
return n > 1 | |
} | |
if n%6 != 1 && n%6 != 5 { | |
return false | |
} | |
sqrtN := int(math.Sqrt(float64(n))) | |
for i := 5; i <= sqrtN; i += 6 { | |
if n%i == 0 || n%(i+2) == 0 { | |
return false | |
} | |
} | |
return true | |
} |
- 首先判断小于 4 的，是否是 2， 3
- 其次如果不能通过 6k + 1 或 6k - 1 表示的，一定不是
- 对于可以用其表示的，则要判断在其平方根之内的形如 6k + 1 或 6k - 1 能否整除它，因为它也可能被另一个素数整除。
这样对于一个大的数来说，判断的次数将显著降低。
