厄拉托西尼(4)〈歷史上第一位測量地球圓周的人〉江銘輝 五夢網

(六) 厄拉托西尼篩

自然數可分為三類即1、質數和合成數三類，質數只有1和本身是因數外，並沒有其他因數，而合成數則有兩個以上大於1的因數。所謂質數表就是造一張表，包括所有不超過已知自然數N的所有質數。如果有一個數m，若不被所有小√m之整數整除，則m本身必為一質數。厄拉托西尼巧妙利用這個原則。發明一種製作質數表的方法，使他的大名在數學史上永垂不朽。這方法雖然簡單，但到今天仍舊適用。其製作方法如下：

首先，把1以外的正整數2,3,4,5,……依序寫下來。

最初的數2為質數。但是，在其後出現的2的倍數都是合成數而非質數。因此，只留下最初的2，而把在其後面出現的2的倍數的數字（譬如4,6,8……）全部刪除。

下一個數3是質數。但是，在其後出現的3的倍數都是合成數而非質數。因此，只留下3，而把在其後面出現的3的倍數的數字都刪除。

其次4這個數已經被消去，它不是質數。再下面的數5，即不是2的倍數，也不是3的倍數，而為質數。因此把5留下，而把在其後面出現的5的倍數的數位全部刪除。

若如此繼續做下去而到達某一個質數P，則小於 的自然數中不被消去而留下的，都是質數。現在我們以100的質數表為例，說明如下：

圖10是一個用厄拉托西尼篩的方法製作的100以下質數表。

圖10：用厄拉托西尼篩的方法製作的100以下質數表。

製作此表，我們只要把10以下的質數的倍數（即2、3、5、7的倍數）刪除就可以，因為10的平方是100，我們用不著再繼續作10到100的刪除工作。

從理論上說，用厄拉托西尼篩法可以造出任意範圍內的質數表，厄拉托西尼自己就曾造出第一張1000以下的質數表（如圖11）。

圖11：厄拉托西尼製作的1000以下質數表。

儘管用厄拉托西尼篩可作成任意數目的質數表，但是質數的數目究竟是有限或無限大？這個問題早在厄拉托西尼篩發明以前，希臘數學界就出現了一場關於質數是有限個還是無限個的辯論，那時希臘的知識份子很喜歡辯論，而且喜歡通過數學證明來決定勝負。最後由歐幾裡德（Euclid）在他的〈原本〉書中證明了質數有無窮多個，來結束這場爭論。歐幾裡德的證明方法很簡單，他說：如果質數的個數有限，那麼我們就可以把它一一寫出來，譬如：P₁、P₂、P₃、P₄……P_n，但是我們看P₁×P₂×P₃……×P_n+1這個數，顯然不能被P₁、P₂、P₃、……P_n，中的任何數整除，因此除了P₁、P₂、P₃……P_n外，還有一個更大的質數存在。所以質數的個數無限多。

質數既然是無窮多個，有沒有公式將所有質數的分佈表示出來。十八世紀以前許多數學家都嘗試給出質數的表示式，結果都失敗了。

西元1792年，年僅15歲的德國數學家高斯（C.F. Gauss）以剛出版的蘭伯特（J.H. Lambert）質數表為藍本，研究質數的分佈。在這裡我們依數學家蘭道（E.G.H. Landau）以後的慣例，把整數X以前的質數個數寫成π(X)。高斯先把1000分成一組，根據質數表計算各組裡面的質數的個數，發現 （ln t為自然對數）。很巧合地，法國的數學家勒建德（A.M. Legendre）（圖12）在這時候也根據圖13的質數個數分佈表，發現了下面的近似公式，並在1798年發表。

圖12：勒建德（A.M. Legendre，法國人，西元1752～1833年）1798年，他發表專著〈關於數論的研究〉並第一個提出“數論”這個名詞，其後他又提出 的質數個數猜想，1823年證明了費馬大定理n=5是成立的，他也研究〈橢圓函數論〉及歐幾裡德〈原本〉第五公設皆有成就。但他最著名的應是廣泛應用在工程及物理學的“勒建德方程式”（Legrendre equation）勒建德和拉格朗日（J.L. Lagange，法國人，西元1736～1813年）、拉普拉斯（P.S. Laplace，法國人，西元1749～1827年）稱為法國數學界的“3L”。

這兩個式子是否成立，兩位德國和法國的數學名家對他們自己所發現的質數分佈公式都無法證明其是否成立，可見證明它的困難度。最後人們稱 為質數猜想。

圖13： 10⁹以下的π(x)及x/ln x

西元1859年，德國科學院青年院士黎曼（G.F.B. Rieman），他以複變函數理論為工具嘗試對質數猜想作出證明，可惜沒有成功。儘管黎曼當時沒有解決，但他所出的複變函數方法，被希爾伯特（D. Hilbert）（圖14）列為23個世界級數學難題之一。且為後人奠定了質數猜想證明的基礎。三十年後，法國數學家哈達瑪（Hadamard Jacques, 1865～1963）及比利時數學家瓦萊普辛（Vallee Poussin, 1866～1962）分別獨自於1894年及1896年以黎曼複數函數為基礎證明了質數猜想，即證明了 ，從此質數猜想變成了質數定理。

用複變函數這種高等數學來證明質數問題，總有些拐變抹角。它與整數中的質數有什麼關係﹖有沒有不用複數函數的初等證明方法。許多數學家連英國世界一流數學家哈代（Hardy, 1877～1947）都斷言質數定理的初等證明是不可能的。

就在哈代斷言28年之後，挪威和匈牙利的兩位青年數學家賽爾伯格（Atle Selberg, 1917～　）及愛多斯（P. Erdos）同時用初等方法證明了質數定理。

圖10：希爾伯特（德國人，1862～1943年），希爾伯特于1900年的巴黎第二屆國際數學家大會提出著名的23個數學未解問題，揚示了20世紀數學家奮鬥的目標，他研究幾何學基礎論，代數的整數論，也建立希爾伯特空間理論，晚年關心數學基礎。透過符號邏輯及證明論的研究，建立數學的形式主義。