質數是指任何大於 1 的整數，其唯一的因數只有 1 和它本身——而實際上產生質數清單最快的方法，就是執行「埃拉托斯特尼篩法」（Sieve of Eratosthenes），這個演算法幾乎能在瞬間列出 10,000,000 以下的所有質數。最經典的質數測試方法「試除法」，對於小數字運作良好，但隨著 N 增大，速度會變得極為緩慢，因為每個候選數都必須除以所有小於它的質數。篩法則反過來處理這個問題：它不是逐一測試每個數字，而是從 2 到 N 的所有整數出發，有系統地劃掉每個找到的質數的倍數。所有存活下來的數字，保證都是質數。質數產生器採用的就是這個方法，而且它完全在你的瀏覽器中執行，所以不需要安裝任何東西、無需上傳、也不必排隊——你只要輸入一個數字，按下按鈕，完整的質數清單就會連同數量、總和以及找到的最大質數一起顯示出來。
為什麼試除法會隨著數字變大而停滯
大多數人最早學會的就是試除法，它完全正確——你將每個候選數 n 除以從 2 到 √n 的所有整數。如果這些除法中沒有一個能整除，n 就是質數。問題在於工作量。當你處理到數千這個量級時，每個候選數已經需要執行數千次除法，而且大多數候選數最終都是合數。質數定理告訴我們，隨著數字變大，質數會變得稀疏，但永遠不會消失，因此檢查每個非質數候選數的成本會持續攀升。
有一些捷徑能幫上一點忙。你只需要測試較小的質數是否整除，不必測試每個整數，因為合數的因數必然可以化約為質數因數。你也只需要測試到 √n 為止，因為任何大於 √n 的因數必定配對一個小於 √n 的因數。而小質數 2、3 和 5 通常就能在一步之內淘汰大部分候選數。但即便運用了所有這些技巧，每個候選數所需的除法次數，仍然與 √n 以下的質數數量成正比，而這個數字會無限制地增長。對於家庭作業等級的範圍來說還堪用；但對於加密等級的數字，這種方法完全無用。
這正是篩法存在的原因。篩法不是在問「這個單一的數字是不是質數？」，而是問「從 2 到 N 之中，哪些數字沒有小於自身的質因數？」，並且它透過「淘汰法」而非反覆測試來回答這個問題。
埃拉托斯特尼篩法如何列出質數
埃拉托斯特尼篩法是一個用於列出某個固定上限以下所有質數的古老演算法，對於這項工作，它至今仍是最快速的直接方法。整個程序是機械化的。
從整數 2, 3, 4, ..., N 出發。將 2 標記為質數，並劃掉 2 的所有倍數——於是 4, 6, 8, 10 等都消失了。接著移到下一個未被劃掉的數字，也就是 3。將它標記為質數，並劃掉 3 的所有倍數——6, 9, 12, 15 等。移到下一個存活者 5，並劃掉它的倍數。重複這個步驟。當你抵達當前質數的平方時，就可以停止劃掉，只需將剩下的所有未標記數字都標記為質數。
這個方法之所以有效，原理簡單卻極為有力。任何合數 n 都必定有一個質因數 p 滿足 p ≤ √n。這個質因數 p 在篩法的早期階段就會被標記為質數，而 p 的劃掉步驟便會將 n 淘汰。因此，凡是完整通過整輪篩選而存活的數字，都沒有任何質因數——也就是說，它除了 1 和自身之外沒有其他因數——這代表它就是質數。
篩法的成本眾所周知地接近線性。每個整數最多只會被劃掉寥寥數次，執行時間大約是 O(N log log N)。當 N = 1,000,000 時，它比試除法快上數百倍；當 N = 10,000,000 時，差距更為驚人。這就是為什麼質數產生器底層引擎採用篩法，也正是它能夠在幾乎瞬間回傳數百萬個質數、卻完全不需要伺服器端運算的原因。
如何使用質數產生器
這就是實作的部分。這個工具在你的瀏覽器中執行，所以一切都在本地端進行，不需要安裝或註冊。完整的操作步驟簡短而明確。
- 選擇模式。如果你想列出所有不超過某個指定上限的質數，請選「Primes up to N」（N 以下的質數）；如果你想要剛好 N 個依序排列的質數，請選「First N primes」（前 N 個質數）。
- 在輸入框中輸入你要的 N 值。對於第一種模式，這是上限（最高 10,000,000）；對於第二種模式，這是你想要的質數個數（最高 100,000）。
- 按下 Generate primes（產生質數），或直接按 Enter 鍵。完整的質數清單便會出現。
- 查看結果。在清單下方，你會看到總數、結果中所有質數的總和，以及所產生的最大質數。
- 如有需要可複製清單。只需一個點擊，整份質數清單就會進入你的剪貼簿，方便你貼到試算表、程式碼檔案或作業文件中。
在兩種模式之間做選擇
這兩種模式解決的是不同的問題，選對模式能讓你不必事後質疑輸出結果。以下是並列對照表。
| 你想問的問題 | 應選的模式 | 範例輸入 | 你會得到的結果 |
|---|---|---|---|
| 哪些質數 ≤ N？ | Primes up to N | 100 | 100 以下全部 25 個質數，最後一個是 97 |
| 前 N 個質數是哪些？ | First N primes | 25 | 前 25 個質數，最後一個是 97 |
| 列出小範圍內的質數 | Primes up to N | 1000 | 一千以下的所有質數 |
| 第 1000 個質數是多少？ | First N primes | 1000 | 最後一個項目是 7919 |
| 產生一張長型的參考表 | Primes up to N | 1,000,000 | 一百萬以下的所有質數 |
| 依位置找出特定質數 | First N primes | 10,000 | 前 10,000 個質數，最後一個是 104,729 |
對於大多數家庭作業和參考用途來說，「Primes up to N」是最直覺的選擇，因為它直接對應「列出此數字以下的質數」這個問題。至於基準測試程式碼、Project Euler 類型的題目，以及檢查知名基準值，「First N primes」通常才是你想要的，因為它讓你能夠直接問「第 N 個質數」。兩種模式都會提供結果中的個數、總和與最大質數，所以隨時都有具體的數值可以和手算結果互相比對。
質數真正派上用場的地方
質數不只是一種練習。它會出現在你意想不到的地方，而快速產生質數在這些情境中都很有用。
教師和學生在介紹數論、製作因數分解樹、練習整除性或分解合數時，會用到質數清單。程式設計師則將質數產生器同時用於基準測試——對幾百萬以內的數字執行篩法是經典的效能練習——以及作為雜湊表、偽隨機序列和 Project Euler 類題目的基礎元件。密碼學最依賴大型質數。RSA 演算法保護了大部分的網路流量，它仰賴的正是分解兩個極大質數乘積的實際困難度。快速產生測試用的質數是撰寫與測試這類程式碼的一部分工作。
除了實務用途之外，質數也適合用來檢查其他工具的正確性。如果你在驗證一個因數分解工具、最大公因數工具或任何其他數論程式，只要產生一小份質數清單，再把個別項目餵入受測工具，就能快速發現迴歸問題。此外，孿生質數這類趣味現象——例如 11 與 13，或 17 與 19——會一再出現，因為即便質數越來越稀疏，它們也永遠不會真正用盡。
用來驗證結果的實用參考值
有幾個著名的基準質數值得記在腦中（或釘選在備忘錄裡），因為它們能讓你瞬間用手驗證任何輸出。
| 位置或範圍 | 預期值 | 用來檢查 |
|---|---|---|
| 第 25 個質數 | 97 | 確認「前 25 個質數」或「100 以下的質數」 |
| 100 以下的質數（個數） | 25 | 同上 |
| 30 以下的質數（個數） | 10 | 快速的模式測試 |
| 第 100 個質數 | 541 | 「前 N 個質數」的中段基準 |
| 第 1000 個質數 | 7919 | 常見的 Project Euler 目標 |
| 第 10,000 個質數 | 104,729 | 大型基準的健全性檢查 |
| 第 100,000 個質數 | 1,299,709 | 支援個數的上限 |
「First N primes」模式讓你可以指定精確的 N 來重現上述任何一項結果，而「Primes up to N」則讓你可以透過對應的上限來重現這些個數。如果某個工具回傳的個數與上表不符，你就立刻抓到一個 bug。質數產生器的設計使其輸出內部一致——個數、總和與最大質數皆與清單吻合，而清單本身也與所選的模式相符——因此當你以上述任一著名數值作為基準，便能信任其餘輸出，而不必逐一重新檢查每個項目。