埃拉托斯特尼篩法

古希臘數學家埃拉托斯特尼 (Eratosthenes 約公元前200年)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

好一個篩子

埃拉托斯特尼 (Eratosthenes 約公元前200年) 是古希臘的數學家,他提出一個尋找素數 (Prime Number) 的方法,我們現在亦常用,稱之為「埃拉托斯特尼篩法 (Sieve of Eratosthenes)」,簡稱「篩法」或 「埃氏篩」。這算法 (Algorithm) 最早記載於公元 1 世紀古希臘數學家尼科馬霍斯 (Nichomachus 約60 - 約120) 的著作《算術入門》中。

例:我們找尋 100以內的所有素數。

方法是:

先把 1-100的數列寫出來,大家亦可配合十行表,方便書寫。

接著把數 1 刪除,因 1 是單位 (Unit) ,不屬於素數或合數 (Composite Number)。

把剩餘中最小的數字圈起 (如 2),把它的其它倍數刪除。

重覆上一步驟 (在 3、5、7各數),直至最小該數的平方大於我們的上限 (11的平方為 121),如 100。

把餘下的整數全圈起來。所有圈起來的都是素數了。

 

所以 100 以內的素數有 2 、 3 、 5、 7 、 11 、 13 、 17 、 19 、 23 、 29 、 31 、 37 、 41 、 43 、 47 、 53 、 59 、 61 、 67 、 71 、 73 、 79 、 83 、 89 和 97 合共 25 個。

大家可試以「篩法」尋找 1-200 、 1- 1000 甚至 1 -10000 的素數。

 

素數表的歷史

那麼讓我們談談研究素數中一樣必不可少的工具了,那便是素數表 (Prime Number List) 和數的素因子分解表 (Prime Factorization Table)。

最先布蘭加 (Brancker) 於 1668年給出一個 100000 以內的數的最小因子表,這是我們看見規模較大的數表。

古加 (Kruger) 於 1748年 給出 100000 以內的素數表。

蘭伯特 (Johann Heinrich Lambert 1728 - 1777) 於 1770年給出 102000 以內的數的最小因子表。

費爾基 (Filkel) 於 1776年給出 408000 以內的數的最小因子表。

維加 (Vega) 於 1797年給出 400031 以內的素數表。

查歷 (Charnec) 於 1811年給出 102000 以內的數的素因子表。

布基赫治 (Burckhardt) 在 1816至 1817年間給出 3036000 以內的數的最小因子表。

以後數表的上限漸漸擴大,到了 1856年,我們已有 6000000 以內的素數表,之後又擴展至 9000000。

古尼克 (Kulik) 製造了 100330220 內的整數 (不被 2, 3 , 5 整除的) 的因子表。他花了 20年時間才完成此表,最後在他逝世 (1863年) 之後,後人把這表,共八卷 4212頁的材料交付維也納科學院,時間為 1867年 2月。

由於電腦普及,許多數表被製成磁帶。只要區間數值不大,即使我們即時以埃拉托斯特尼篩法也可很快地找到當中的素數。是故素數表的作用已漸漸被取代了。但本網亦預備了《首 100000 個素數》的素數表,歡迎瀏覽。

難倒大素數

正是因為電腦技術的飛快發展,我們尋找素數的目標已轉向一些較大的整數,從下列名稱大家可知一二:

1. 超大素數 (Titanic Prime) - 擁有過千數位的素數;

2. 超霸素數 (Gigantic Prime) - 擁有過萬數位的素數;

3. 百萬位級素數 (Megaprime) - 擁有過百萬數位的素數 。

自 20 世紀 80 年代,數學家耶斯 (Samuel Yates) 創製超大素數一詞起,我們已預見更大的素數的出現。耶斯去世以後,數學家卡特維爾 (Chris Caldwell) 成為這些巨大素數的收藏家,其網站 (見頁底的參考文獻及網址) 亦有定期更新大素數的發現情況。我們在 2000 年時,只有 1 個百萬位級素數,這是 1999 年發現的第 38 個梅森素數 (Mersenne Prime),可參看《一切由完全數開始 - 梅森數》。但到 2005 年,已有 8 個百萬位級素數;到了 2010年,更增加至 31 個,由此我們相信這百萬位級素數是會不斷 地增加,且越來越快。想一想找一個這麼大的素數,用「埃拉托斯特尼篩法」的步驟有多少?可不可以?當然是不可以,怎麼辦?這我們得運用更多的數學知識了。《不斷改進的方法》一文會詳加論述,但內容涉及同餘 (Congruence) 和費馬小定理 (Fermat's Little Theorem) 的知識,若有需要,本網亦備有相關前置知識的介紹,觀迎參看。

 

參考文獻及網址

Caldwell, C. K. "The List of Largest Known Primes Home Page." http://primes.utm.edu/primes/.

Caldwell, C. K. "The Top Twenty Home Page." http://primes.utm.edu/top20/home.php.

Ribenboim, P. "The Little Book of Bigger Prime" , New York: Springer-Verlag, 1991