素數判別法

判斷素合

判斷一數 n 的素性 (Primality) ，即是指判斷該數是素數 (Prime Number) ，還是合數 (Composite Number)。素數是指該 2 或以上的整數 (Integer) 除 1 或本身以外沒有別的因子 (Divisor)。故我們可以用一些比 n 小的整數來試除 (Trial Division) ，當然是由小至大吧。看看是否可以整除，若有數可以，即 n 是合數；反之， n 為素數。

於是我們發現試除時只要試「不大於 n 的平方根的素數」便可以。為什麼？就讓我來說明吧！

先是只試素數，原因很簡單，因為合數均可以分解成一些素因子的乘積，如 6 = 2*3。若 n 真的為一合數 (如 6) 的倍數，必然是其素因子 (如 2) 的倍數，且我們在試除較小的素數，應可整除，是故以合數試除是多此一舉的。

再說只用試至 n 的平方根，解釋則相對複雜一點。

若 n > 1 且為一素數，則顯然不大於 n 的平方根的所有素數不能整除 n，反過來說，若 n 不是素數，設 p 為 n 的最小素因子，即 1 < p < n。這時我們會有 p 不少於 n 的平方根，否則，即 p 大於 n 的平方根，因為 n/p > 1且是一自然數，故存在素因子 p₁，因為 p 為最小素因子，所以有 p₁ 不少於 p，但同樣 p₁也比 n 的平方根大。看 n = p* p₁*Q (Q 可以為 1)，n > ( n 的平方根)* (n 的平方根) = n，因而矛盾。故 p 一定不少於 n 的平方根。

由此我們測試的數字可少得多了，如判斷 1997 的素性：

我們先計算 1997 的平方根，即 44.687805943008658746325418416237。

少於上數的平方根的素數有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 合十四素數。故以之一一試除。

1997 / 2 = 998 ..... 1，1997 / 3 = 665 ...... 2， 1997 / 5 = 399 ...... 2，一直至 1997 / 43 = 46 ...... 19 均不能整除。

故 1997 是一素數。 (即 1997年是一素數年 (Prime Year)，詳見《今年是素數年》。)

方法有疑難

上述判別法，我們老早便認識，但大家未必知這方法也有問題：

第一，我們在測試一數 n 時，必先找到所有少於 n 的平方根的素數作除數。因為 2 以外的素數皆是奇數，我們亦可以奇數代替素數來作試除，但這無疑是增加了計算量。

第二，我們可在以心算判斷 n 是否一些素數 (如 2, 3, 5 或 11) 的倍數，快些為一些合數作判。方法詳見《倍數判別法》一文。

第三，數愈大，其測試過程和步驟數則愈多。所以當我們判斷一很大的數 (如 n > 10¹⁰ ) 時，所花時間則很多。

第四，對於一些素因子不多、或最小素因子 (Least Prime Factor) 較接近 n 的平方根的合數，其判斷時間則更長。

因此我們必須尋找一更有效的素數判別法則和分解大數的方法。

接下來多篇文章，我會為大家詳談這一點。