素數判別法

判斷素合

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

但若 n 真的為一素數,意味著自 2 至 n-1 均不可整除 n 。這樣的要證實,自 2 至 n-1 來試除 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且是一自然數,

故存在素因子 p1,因為 p 為最小素因子,所以有 p1 不少於 p,但同樣 p1也比 n 的平方根大。

看 n = p* p1*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 > 1010 ) 。

 

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