埃拉托斯特尼篩法
古希臘數學家埃拉托斯特尼 (Eratosthenes 約公元前200年)
(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )
好一個篩子
埃拉托斯特尼 (Eratosthenes 約公元前200年) 是古希臘的數學家，他提出一個尋找素數 (Prime Number) 的方法，我們現在亦常用，稱之為「埃拉托斯特尼篩法 (Sieve of Eratosthenes)」，簡稱「篩法」。這算法最早記載於公元 1 世紀古希臘數學家尼科馬霍斯 (Nichomachus 約60 - 約120) 的著作《算術入門》中。 例：我們找尋 100以內的所有素數。 |
 |
方法是：
先把 1-100的數列寫出來，大家亦可配合十行表，方便書寫。
接著把數 1 刪除，因
1 不屬於素數或合數 (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 的素數。
素數表的歷史
那麼讓我們談談研究素數中一樣必不可少的工具了，那便是素數表和數的因子分解表。
最先布蘭加 (Brancker) 於 1668年給出一個 100000 以內的數的最小因子表，這是我們看見規模較大的數表。
古加 (Kruger) 於 1748年 給出 100000 以內的素數表。
蘭伯特 (Lambert) 於 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 個，而且我們相信這是會不斷增加，且越來越快。想一想找一個這麼大的素數，用「埃拉托斯特尼篩法」的步驟有多少？可不可以？當然是不可以，怎麼辦？下回分解。
參考文獻及網址：
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
