素數判別法

判斷素合

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

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

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

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

若 n > 1 且為一素數，則顯然不大於 n 的平方根的所有素數不能整除 n，

反過來說，若 n 不是素數，設 p 為 n 的最小素因子 (Least Prime Factor)，即 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 以外的 所有素數皆是奇數，我們亦可以奇數代替素數來作試除，但這無疑是增加了計算量。別小看這個替換，因為在大數空間中素數密度 (Density of Primes) 變得稀疏，增加了的計算量可以是原本的數十倍，甚至數千倍的。

第二，對於一些素因子不多、或最小素因子較接近 n 的平方根的合數，其判斷時間則很長。

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

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