一個質數是一個大於1,且無法找到除了自己本身和1之外的自然數能整除它的自然數。舉例來說,2、3、5、7、11、13和17均為質數。質數是數學上的難題,即便數學已經過幾千年的發展,卻也還是無法找出一個能完美產生出質數的函數。在學習寫程式的過程中,儘管在現實社會中幾乎用不到,我們還是會常常遇到判斷質數或是尋找質數的問題。那麼,究竟要如何利用程式來處理判斷質數和尋找質數呢?



判斷質數

既然質數無法被除了自己本身和1之外的自然數整除,假設某數為#{{N}}#,且#{{N \gt 2}}#,那我們就可以寫一個計次範圍是#{{2}}#到#{{N - 1}}#(包含#{{2}}#和#{{N - 1}}#)的迴圈,來一個一個測試#{{N}}#是否能夠被這個範圍的自然數整除。如果可以的話,表示#{{N}}#不為質數;如果不行的話,則表示#{{N}}#為質數。以Rust程式語言為例,程式如下:

當然,這種判斷某數是不是質數的方式是最蠢又最慢的方式,完全不建議使用。那我們該怎麼優化它呢?首先,我們都知道所有的偶數除以#{{2}}#都可以整除,且可以被#{{2}}#整除的正整數,除了#{{2}}#本身之外必定不是質數。所以在測試#{{N}}#是否為質數時,我們在迴圈內可以完全略過除以偶數的檢查步驟,讓判斷時間減少至將近一半。程式改寫如下:

再來,根據古希臘數學家Sieve of Eratosthenes(埃拉托斯特尼)的質數篩法(埃拉托斯特尼篩法),我們的計次迴圈其實不必計到#{{N - 1}}#,只需計到#{{\sqrt N}}#即可。為什麼呢?我們可以通過反證法,來證明「若#{{N}}#是合數(非質數),且這個合數的因數皆#{{\gt \sqrt N}}#」是錯的,即:
#{{{
\text{若$N$為合數,且有$r$個因數($r \geq 2$)} \nonumber \\
\text{反證明 $P_{1},P_{2},\cdots,P_{r} \gt \sqrt N$ }
}}}#
#{{{
N = P_{1}P_{2}{\cdots}P_{r} \geq N^{r \over 2} \text{ } (\because {r \over 2} \geq 1) \nonumber \\
N^{r \over 2} \geq N \nonumber \\
\because N \geq N^{r \over 2} \text{ 和 } N^{r \over 2} \geq N \text{ 矛盾 } \nonumber \\
\therefore 反證成立
}}}#

因此,「若#{{N}}#是合數,其必定會有至少一個因數#{{\leq \sqrt N}}#」,於是我們的計次迴圈其實不必計算到#{{N - 1}}#,只需計算到#{{\sqrt N}}#即可。程式再次修改如下:

若使用「#{{6n}}#, #{{6n + 1}}#, #{{6n + 2}}#, #{{6n + 3}}#, #{{6n + 4}}#, #{{6n + 5}}#且#{{n \in \mathbb{N}}}#」,來表示所有整數。則#{{6n}}#必可用「#{{6}}#」、「#{{3}}#」或「#{{2}}#」整除;#{{6n + 2}}#和#{{6n + 4}}#必可用「#{{2}}#」整除;#{{6n + 3}}#必可用「#{{3}}#」整除。所以質數只能是#{{6n + 1}}#或是#{{6n + 5}}#(注意這裡並不是說#{{6n + 1}}#和#{{6n + 5}}#就是質數),而#{{6n + 5}}#也可以表示為#{{6(n + 1) - 1}}#。於是我們又可以繼續優化程式:

優化到這裡就夠用了,如果還想要更快的話,可以參考本篇文章最後提到的查表優化。實際上,質數的測試還有一些透過複雜的數學推導出來的方法能夠使用,不過由於實作起來麻煩許多,也很難理解,本篇文章就不去探討了。

尋找質數

如果我們想要尋找某整數範圍中的質數,最簡單的作法就是將該範圍中的整數一一找出來,再使用「is_prime_number」函數判斷它是否為質數。程式如下:

當然還可以做點小小的優化,在迴圈外就過濾掉偶數的部份,減少迴圈執行的次數。程式如下:

查表優化

在檢查某數#{{N}}#是否為質數的時候,我們只需去測試是否能找到一個比#{{N}}#小的質數來整除它,而不必去嘗試所有的#{{6n + 1}}#或是#{{6n + 5}}#。但是我們要如何知道比#{{N}}#小的質數到底是哪些呢?那就是事先建好小質數的質數表啦!花費一些記憶體空間,利用小質數的質數表來快速找出大質數是個很划算的交易。

那我們的小質數的質數表需要建多大呢?請注意,根據埃拉托斯特尼篩法,我們在測試#{{N}}#是否為質數的時候最大只會去嘗試除到#{{\sqrt N}}#。如果我們想要讓#{{N}}#的能夠完全與已知的質數作除法測試運算的話,假設#{{N}}#的型別是32位元的整數,那麼它最大能表示的數值為:

#{{{ 2^{32-1} - 1 = 2^{31} - 1 \text{ } ( = 2147483647 ) }}}#

也就是說,大概會需要取到#{{ \leq floor(\sqrt { 2^{31} }) = floor(2^{31 \over 2}) = floor(2^{15.5}) = 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 }}#個位元組的空間。這實在太多了,在一般情況下根本不切實際!

所以,我們還是採取最初的方案,建造約4313個質數的質數表來優化程式就好。優化後的程式如下: