生成所有 32 位元質數（第一部分）

背景

本文記錄了一位開發者挑戰在 Linux 環境下，利用 C 語言快速生成所有 32 位元無符號整數範圍內的質數，並將結果以二進位格式寫入檔案。作者從最基礎的試除法出發，逐步探討如何透過輪式分解等數學特性來優化演算法，目標是在 1GB 記憶體限制內達成最高效率。

社群觀點

在 Hacker News 的討論中，社群成員針對效能優化與演算法選擇展開了深入探討。許多評論者指出，雖然作者採用的試除法與輪式分解是理解質數生成的好起點，但在實務上，米勒-拉賓質數判定法能提供更驚人的速度。有網友分享在瀏覽器環境下使用該演算法，僅需三分鐘即可完成所有 32 位元質數的判定。針對米勒-拉賓這類機率性演算法的準確性疑慮，討論中也給出了明確解答：對於 32 位元甚至高達 82 位元的整數，只要選對特定的見證數集，該演算法便能從機率性轉為完全確定性，保證不會出現誤判。

除了判定演算法，記憶體管理與篩法變體也是討論焦點。有觀點認為，分段式埃拉托斯特尼篩法在維持高效能的同時，能大幅降低記憶體需求，僅需儲存至目標值平方根大小的質數表即可運作。更有進階討論提到「偽平方篩法」，能將記憶體需求進一步壓縮至對數等級。此外，關於將結果寫入檔案這一要求，社群內出現了不同聲音。部分開發者認為 I/O 操作會成為效能瓶頸，掩蓋了演算法本身的優化成果；但也有人認為這是一個有趣的實務約束，能強迫開發者思考如何平衡運算與資料傳輸。

最後，針對極致效能的追求，社群推薦了如 primesieve 等現成的成熟工具，其生成速度已達毫秒等級。對於程式碼的簡潔性，則有愛好者分享了極簡的 Python 實作，雖然在處理大規模數據時記憶體消耗較大，但在解決如 Project Euler 等數學競賽問題時，其開發效率與邏輯美感仍具有不可替代的價值。

延伸閱讀

• primesieve: 目前已知最快的質數生成工具之一，能在極短時間內處理 32 位元範圍。
• Prime Grid Explorer: 一款基於 JavaScript 實作的視覺化工具，利用米勒-拉賓判定法展示高達 82 位元的質數。
• Pseudosquares Sieve: 相關學術論文，探討如何將篩法的記憶體需求降低至 log 平方等級。
• Tromp's C Sieve: 一份精簡且高效的 C 語言篩法實作範例。