一个质数(Prime)是一个大于 1,且无法找到除了自己本身和 1 之外的自然数能整除它的自然数。举例来说,2、3、5、7、11、13 和 17 均为质数。质数是数学上的难题,即便数学已经过几千年的发展,却也还是无法找出一个能完美产生出质数的函数。在学习写程序的过程中,尽管在现实社会中几乎用不到,我们还是会常常遇到判断质数或是寻找质数的问题。那么,究竟要如何利用程序来处理判断质数和寻找质数呢?

判断质数

既然质数无法被除了自己本身和 1 之外的自然数整除,而 #{{2}}# 被归类在质数,假设某数为 #{{N}}#,且 #{{N \gt 2}}#,那我们就可以写一个计次范围是 #{{2}}# 到 #{{N - 1}}#(包含 #{{2}}# 和 #{{N - 1}}#)的循环,来一个一个测试 #{{N}}# 是否能够被这个范围的自然数整除。如果可以的话,表示 #{{N}}# 不为质数;如果不行的话,则表示 #{{N}}# 为质数。程序如下:

当然,这种判断某数是不是质数的方式是最蠢又最慢的方式,完全不建议使用。那我们该怎么优化它呢?首先,我们都知道所有的偶数除以 #{{2}}# 都可以整除,且可以被 #{{2}}# 整除的正整数,除了 #{{2}}# 本身之外必定不是质数。所以在测试 #{{N}}# 是否为质数时,我们在循环内可以完全略过除以偶数的检查步骤,让判断时间减少至将近一半。程序改写如下:

再来,试除的循环其实只需要做到 #{{\sqrt N}}#。由于合数 #{{N}}# 可以写成 #{{a \times b}}#,其中 #{{a, b \gt 1}}#,假如两个因数都大于 #{{\sqrt N}}#,乘积就会大于 #{{N}}#,和原本的条件矛盾。

因此,合数 #{{N}}# 至少有一个介于 #{{2}}# 和 #{{\sqrt N}}# 之间的因数。我们只要将循环的上界改成 #{{\lfloor \sqrt N \rfloor}}# 即可。程序再次修改如下:

还没完呢!若使用「#{{6n}}#, #{{6n + 1}}#, #{{6n + 2}}#, #{{6n + 3}}#, #{{6n + 4}}#, #{{6n + 5}}# 且 #{{n \in \mathbb{N^0}}}#」,来表示所有非负整数。则 #{{6n}}# 必可用「#{{6}}#」、「#{{3}}#」或「#{{2}}#」整除;#{{6n + 2}}# 和 #{{6n + 4}}# 必可用「#{{2}}#」整除;#{{6n + 3}}# 必可用「#{{3}}#」整除。因此,大于 #{{3}}# 的质数只可能是 #{{6n + 1}}# 或 #{{6n + 5}}#。这两种形式也可能是合数,例如 #{{25}}# 和 #{{35}}#。其中 #{{6n + 5}}# 还可以写成 #{{6(n + 1) - 1}}#。

于是我们又可以继续优化程序:

优化到这里就够用了,如果还想要更快的话,可以参考本篇文章最后提到的查表优化。实际上,质数的测试还有一些透过复杂的数学推导出来的方法能够使用,不过由于实作起来麻烦许多,也很难理解,本篇文章就不去探讨了。

寻找质数

如果我们想要寻找某个整数范围中的质数,可以从范围起点与 2 之中取较大的数,逐一判断到终点为止。起点大于终点时,结果就是空的。

Java 使用 long 做循环计数,Go 则在计数到终点时结束循环,这样就能处理整数类型的上界。TypeScript 的两个参数都须是 Number.isSafeInteger 能辨识的安全整数。程序如下:

当然还可以做点小小的优化。范围里若包含 2,就先把 2 放进结果,接着从范围内大于等于 3 的第一个奇数开始,每次增加 2,就能减少约一半的判断次数。程序如下:

如果按数值的大小寻找质数,就可以用先前找到的质数协助判断下一个数。先把范围里的 2 和 3 放进结果,接着从大于等于 5 的第一个奇数开始,检查除以 6 后余数为 1 或 5 的候选值。

对于小于循环起点的因数,我们先用前面介绍的方式,每次检查一组 #{{6n - 1}}# 和 #{{6n + 1}}#。从起点开始,则用已找到的质数试除。两段都只需试到平方根,程序使用 i <= n / i 判断上界,这样可以避免计算平方时溢出。

最终的代码如下:

以范围 -1 到 7 为例,运行上述各种写法会得到相同的结果。

[2, 3, 5, 7]

甚至我们也可以把整数范围起始点之前的质数也偷偷记下来沿用,只不过这样会需要消耗额外的内存空间就是了。

查表优化

在检查某数 #{{N}}# 是否为质数的时候,我们只需去测试是否能找到一个比 #{{N}}# 小的质数来整除它,而不必去尝试所有的 #{{6n + 1}}# 或是 #{{6n + 5}}#。但是我们要如何知道比 #{{N}}# 小的质数到底是哪些呢?那就是事先建好小质数的质数表啦!花费一些内存空间,利用小质数的质数表来快速找出大质数是个很划算的交易。

上面的小节介绍的寻找质数的方式,做到后来就是一边建质数表,一边用这个质数表来协助判断之后的整数是不是质数。其实我们也可以在一开始(代码正在撰写时)就先把小质数的质数表建出来,以 Hard Code 的形式写死在代码中,以此来优化判断某数是不是质数的效率。不过当然,这个质数表也不适合被建得太大。

那我们的小质数的质数表需要建多大呢?请注意,根据埃拉托斯特尼筛法,我们在测试 #{{N}}# 是否为质数的时候最大只会去尝试除到 #{{\sqrt N}}#。如果我们想要让 #{{N}}# 能够完全与已知的质数作除法测试运算的话,假设 #{{N}}# 的类型是 32 比特的整数,那么它最大能表示的数值为:

#{{{
\begin{alignedat}{2}
2^{32-1} - 1 &{}={}&& 2^{31} - 1 \text{ } \\
\text{( } &{}={}&& 2147483647 \text{ )}
\end{alignedat}
}}}#

也就是说,大概会需要取到

#{{{ \leq \lfloor{\sqrt { 2^{31} }}\rfloor = \lfloor{2^{31 \over 2}}\rfloor = \lfloor{2^{15.5}}\rfloor = 46340 }}}#

的所有质数。

小于等于 46340 的质数有多少个呢?根据法国数学家 Adrien-Marie Legendre(勒让德)的猜想,#{{ \leq x }}# 的质数数量 #{{ \pi (x) }}# 大概等于:

#{{{
x \over { \ln (x)}
}}}#

将 46340 代入后,

#{{{
{ 46340 \over { \ln (46340)} } \approx 4313
}}}#

所以我们的质数表大概会有 4313 个质数,占掉 #{{ {{4313 \times 32} \over 8} = 17252 }}# 个字节的空间。这个内存耗费量其实还蛮小,却可以让程序运算速度快上许多,真是非常划算!

但若我们将 #{{ \leq 2^{31} - 1 }}# 的所有质数都建成质数表的话,大概会有 #{{ { 2147483647 \over { \ln (2147483647)} } \approx 99940774 }}# 个质数,需要占掉 #{{ {{99940774 \times 32} \over 8} = 399763096 }}# 个字节的空间。这实在太多了,在一般情况下根本不切实际!

所以,我们还是采取最初的方案,建造小于等于 46340 的质数表来优化程序就好。实际上这样的质数共有 4792 个,由于 2 可以另外判断,以下程序的质数表只存了 4791 个。优化后的程序如下: