一個質數(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}}#是否為質數時，我們在迴圈內可以完全略過除以偶數的檢查步驟，讓判斷時間減少至將近一半。程式改寫如下：

再來，根據古希臘數學家Sieve of Eratosthenes(埃拉托斯特尼)的質數篩法(埃拉托斯特尼篩法)，我們的計次迴圈其實不必計到#{{N - 1}}#，只需計到#{{\sqrt N}}#即可。為什麼呢？我們可以通過反證法，來證明「若#{{N}}#是合數(有兩個以上的因數)，且這個合數的因數皆#{{\gt \sqrt N}}#」是錯的，即：

#{{{
\begin{eqnarray}
\text{若$N$為合數，且有$r$個因數($r \geq 2$)} \nonumber \\
\text{反證明 $P_{1},P_{2},\cdots,P_{r} \gt \sqrt N$ }
\end{eqnarray}
}}}#

#{{{
\begin{eqnarray}
N = P_{1} \times P_{2} \times \cdots \times P_{r} > N^{r \over 2} \nonumber \\
N^{r \over 2} \geq N \text{ } (\because {r \over 2} \geq 1) \nonumber \\
\end{eqnarray}
}}}#

#{{{
\begin{eqnarray}
&\because& N > N^{r \over 2} \text{ 和 } N^{r \over 2} \geq N \text{ 矛盾} \nonumber \\
\nonumber \\
&\therefore& \text{ 反證成立}
\end{eqnarray}
}}}#

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

還沒完呢！若使用「#{{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}}#」整除。所以質數只能是#{{6n + 1}}#或是#{{6n + 5}}#(注意這裡並不是說#{{6n + 1}}#和#{{6n + 5}}#就是質數)，而#{{6n + 5}}#也可以表示為#{{6(n + 1) - 1}}#。

於是我們又可以繼續優化程式：

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

尋找質數

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

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

不過這樣子做其實也還是挺暴力的。事實上，一個合數的因數，必定至少有一個質數，也就是說，我們可以重複利用先前找出的質數，來判斷之後的整數是不是質數。至於先前用來判斷某數是否為質數的函數就不要再去呼叫了，把該函數的程式碼內聯(inline)進來，整合在一起吧！

由於我們實作的函數允許在尋找質數的時候去控制數值範圍的起始點，所以不一定會從最小的幾個質數(2, 3, 5,...)開始產生。因此在使用已知質數表來協助判斷質數時，要先去判斷整數開根號之後是否會大於或等於質數表中最小的質數，如果會的話才有辦法查表(因為如果整數開根號小於質數表中最小的質數，那質數表中的數值都在埃拉托斯特尼篩法的範圍外)。且由於質數表很可能會缺最前面的幾個質數，所以除了查質數表外，還要用先前介紹的方式去判斷質數來彌補質數表缺的最前面的幾個質數。

最終的程式碼如下：

甚至我們也可以把整數範圍起始點之前的質數也偷偷記下來沿用，只不過這樣會需要消耗額外的記憶體空間就是了。

查表優化

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

上面的小節介紹的尋找質數的方式，做到後來就是一邊建質數表，一邊用這個質數表來協助判斷之後的整數是不是質數。其實我們也可以在一開始(程式碼正在撰寫時)就些把小質數的質數表建出來，以Hard Code的形式寫死在程式碼中，以此來優化判斷某數是不是質數的效率。不過當然，這個質數表也不適合被建得太大。

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

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

也就是說，大概會需要取到

#{{{ \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 }}#個位元組的空間。這實在太多了，在一般情況下根本不切實際！

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