秘魯數學家哈拉爾德·赫爾夫戈特在2013年解決了一個有271年曆史的難題時獲得了全球關注：即所謂的哥德巴赫弱猜想，根據該猜想，每個大於5的奇數都可以表示為三個素數之和——例如：3 + 3 + 5 = 11 和 19 + 13 + 3 = 35。
但是，38歲的赫爾夫戈特甚至追溯到更久遠的時代，構思出了埃拉託斯特尼篩法的改進版本，這是一種公元前240年左右提出的、廣受歡迎的素數查詢方法。赫爾夫戈特提出的版本將減少計算機記憶體中物理空間的需求，從而減少為進行該計算而設計的程式的執行時間。
素數就像是“數學的原子”，只能被自身和數字1整除。昔蘭尼的埃拉託斯特尼——一位希臘數學家、天文學家和地理學家，曾任亞歷山大圖書館館長，並因計算地球周長而聞名——也提出了一種實用的方法來識別它們：“篩法”，或過濾器。“像許多其他孩子一樣，我10歲時在小學透過表格學到了這個，”赫爾夫戈特說，他目前是法國國家科學研究中心 (CNRS) 和哥廷根大學的研究員。
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保未來能夠繼續報道關於塑造我們當今世界的發現和思想的具有影響力的故事。
為了用這種篩法確定例如1到100之間的所有素數，必須按數字順序寫下數字列表，並按特定順序開始劃掉它們：首先，是2的倍數（除了2）；然後，是3的倍數，除了3；等等，從下一個未被劃掉的數字開始。在此過程中倖存下來的數字將是素數。該方法可以被公式化為演算法，計算機可以快速執行它。
赫爾夫戈特說，在為一本完整演示哥德巴赫弱猜想的書籍校對測試時，他開始思考——“也許花了太多時間”——關於埃拉託斯特尼篩法的問題。特別是關於它對空間或記憶體的要求。“今天的計算機非常快，也可以並行執行計算。但記憶體仍然是有限的，”赫爾夫戈特解釋道。
康奈爾大學和洛斯安第斯大學的數學家讓·卡洛斯·科爾蒂索斯·伊里亞特表示，為了瞭解一個演算法有多好，必須考慮兩個因素：給定輸入（例如100）的每位元運算元，以及指令執行時要儲存在記憶體中的位元數。“就每位元要執行的運算元而言，埃拉託斯特尼篩法相對有效。它與所考慮的區間大小成比例增長。但是，如果你看看對於大區間[數字]執行的演算法的每個步驟需要儲存在記憶體中的內容，那麼篩法就不再有效了，”他說。
現在，受到對被稱為圓法的百年解析技術的綜合方法的啟發，赫爾夫戈特得以改進埃拉託斯特尼篩法，使其在更少的物理記憶體空間中工作。用數學術語來說：不再需要空間N，現在只需要N的立方根就足夠了。“為了計算高達萬億的所有素數，改進後的篩法需要幾百萬位元，而不是十億位元，”赫爾夫戈特說。該提案的主要思想於7月在布宜諾斯艾利斯舉行的第二十一屆拉丁美洲代數研討會和在巴黎舉行的居住在歐洲的秘魯科學家大會Sinapsis 2016上都進行了展示。
為了理解新篩法的優勢，科爾蒂索斯提供了一個類比。“讓我們假設你是一臺計算機，並且你使用紙張來將資料儲存在你的記憶體中。如果要計算1到1,000,000之間的素數，你需要200令紙（10,000張），而使用赫爾夫戈特提出的演算法，你只需要五分之一令紙（約100張），”他說。
儘管減少空間需求通常意味著算法理論速度上的一些“微小”犧牲，但赫爾夫戈特認為，在某些範圍內，這種不足可以透過主要或專門使用快取記憶體記憶體來抵消或超過，快取記憶體記憶體比主記憶體或RAM小但速度更快。“這取決於應用，”他說。
還有其他用於識別素數的篩法或演算法。但赫爾夫戈特指出，埃拉託斯特尼篩法的不同之處在於，它還可以與其他數學運算（如因式分解）一起使用——因式分解是一種將任何數字分解為素數乘積的技術，並且是用於安全編碼資訊（例如用於進行電子銀行轉賬或線上購物）的密碼學方法的基礎。“因式分解已成為當代文明的關鍵要素，”赫爾夫戈特說。埃拉託斯特尼永遠不會想到這一點。