埃拉托斯特尼篩法（Sieve of Eratosthenes）是最簡單的尋找質數的方法，而免費的質數產生器可在您的瀏覽器中執行該演算法，在不到一秒的時間內列出小於一千萬的所有質數。質數是指大於 1、且僅有 1 與自身兩個因數的整數，因此最前面幾個質數依序為 2、3、5、7、11 與 13，且 2 是唯一的偶數質數。以人工方式檢查像 7919 這樣的單一數字是否為質數，必須將它除以從 2 到其平方根之間的每個整數；對於小數字來說雖然可行，但隨著位數增加很快就會變得繁瑣。篩法則反過來處理這個問題。它不再一次一個地問「這個數字是不是質數？」，而是只問一次「哪些數字可以劃掉？」，幾乎能立即產生小於選定上限的完整質數清單。質數產生器正是完全在您的裝置上本機執行這項作業，因此絕不會上傳任何數字，也沒有伺服器佇列或速率限制需要煩惱。
為何人工測試質數不再實用
試除法是最直觀的方法：拿一個數字，先試著除以 2，再除以 3，再除於 5，如此一路除到其平方根。若都無法整除，該數就是質數。對於兩位數的數字而言，這沒什麼問題，因為只需測試少數幾個小質數，但工作量會快速增加。等到檢查四位數質數時，您可能需要測試大約兩打左右的小因數，而若要用手列出前一千個質數，就會變成一個漫長又容易出錯的下午。
還有一個更微妙的問題：試除法無法有效擴展。您想測試的每個新數字，所需的工作量與前一個數字大致相同，因此產生一整串清單而非單一答案，是這個方法最不擅長的場景。每當目標是一份清單時，就需要不同的做法，而這正是當初設計篩法的初衷。
埃拉托斯特尼篩法為何更快
篩法將「逐一測試每個數字」換成「一次處理整個範圍」。您從 2 開始的整數出發，劃掉所有 2 的倍數，再劃掉所有 3 的倍數，再劃掉所有 5 的倍數，依此類推，直到下一個待處理的質數大於您上限的平方根為止。沒有被劃掉的數就是質數，因為任何小於該上限的合數必定會被它的某個質因數劃掉。
此方法的時間複雜度大約是 O(n log log n)，這種複雜度讓它能在現代瀏覽器上於不到一秒內篩選到數百萬。由於質數產生器完全在您的裝置本機上執行這項演算法，您無需上傳任何資料，也不會因伺服器佇列而變慢，即可享有這樣的效能。整個運作過程保持私密且不受速率限制。
三步驟產生質數清單
- 選擇模式。選擇 小於等於 N 的質數來列出代表您選擇的上限內所有質數，或選擇 前 N 個質數來取得固定數量的質數。第一種模式最適合「1000 以下的所有質數」這類範圍；第二種模式則最適合「前 1000 個質數」這類里程碑。
- 輸入您的 N 並執行產生器。將數字輸入到輸入框中，然後按下 產生質數，或直接按下 Enter。對於 小於等於 N 的質數，最大支援的上限為 10,000,000。對於 前 N 個質數，最大支援的數量為 100,000（第 100,000 個質數為 1,299,709）。超過此範圍會被擋下，以維持頁面的反應速度。
- 讀取結果。輸出面板會顯示完整的質數清單、總數、清單中所有質數的總和，以及找到的最大質數。您可以一鍵複製整份清單，用於試算表、程式練習或學習單中。
在「小於等於 N 的質數」與「前 N 個質數」之間選擇
這兩種模式看起來相似，但回答的是不同的問題，選對模式能省下一個步驟。「小於等於 N 的質數」是以範圍為基礎：給它像 1000 這樣的上限，它就會回傳從 2 到 997 之間的所有質數。對於以大小為描述方式的問題——例如「找出小於一百萬的所有質數」或「5000 以下最大的質數是什麼？」——這就是正確的選擇。輸出會自然地由您的 N 所限制，因此您可以預先知道最大的質數。
「前 N 個質數」則是以數量為基礎：給它像 100 這樣的目標數量，它就會回傳 2、3、5、7、……、541。對於里程碑、跨範圍比較，以及在意順序位置的任務而言，這是正確的選擇，例如確認第 1000 個質數為 7,919。在內部，這個工具會使用一個經過驗證的第 N 個質數上限公式，來決定要篩選到多遠，因此結果是精確的而非估算值。
| 您想回答的問題 | 最佳模式 | 範例輸入 | 您會得到的結果 |
|---|---|---|---|
| 小於某個大小上限的所有質數 | 小於等於 N 的質數 | N = 100 | 從 2 到 97 的全部 25 個質數 |
| 依序的特定數量質數 | 前 N 個質數 | N = 25 | 2、3、5、……、89、97 |
| 為一個較大的數值範圍列出質數 | 小於等於 N 的質數 | N = 10,000 | 所有不超過 10,000 的質數，附帶總和與最大值 |
| 依位置找出第 N 個質數 | 前 N 個質數 | N = 1,000 | 前 1000 個質數，最後一個為 7,919 |
如何一眼驗證任何質數清單
無論何時工具給您一份清單，花幾秒鐘檢查最前面與最後面幾個值，就能抓出大部分的錯誤。有幾個錨點值得記住：100 以下剛好有 25 個質數，而 30 以下剛好有 10 個質數，因此對於這些範圍而言，任何「結尾是 97」或「結尾是 29」的清單都是正確的。第 25 個質數是 97、第 100 個質數是 541、第 1000 個質數是 7,919，而第 10,000 個質數是 104,729。若您「前 100 個質數」的輸出結尾不是 541，就代表哪裡出了問題。
您也可以利用質數定理（Prime Number Theorem）作為粗略的大小檢查。粗略來說，小於 n 的質數個數大致以 n 除以 n 的自然對數成長，這是一個有用的數量級估計，能幫助您揪出明顯錯誤的答案。質數會隨著數字變大而變得稀疏，這就是為什麼上限 10,000 內含 1,229 個質數，而上限 100,000 內含 9,592 個質數；而像孿生質數（例如 11 與 13，或 17 與 19）這類趣味現象，則會在各種尺度上持續出現。
| 錨點 | 數值 |
|---|---|
| 100 以下的質數個數 | 25 |
| 30 以下的質數個數 | 10 |
| 第 25 個質數 | 97 |
| 第 100 個質數 | 541 |
| 第 1000 個質數 | 7,919 |
| 第 10,000 個質數 | 104,729 |
| 「小於等於 N 的質數」模式的最大 N | 10,000,000 |
質數清單在實際工作中的應用
質數不僅僅是課堂上的趣味題材。教師與學生會將質數用於數論課程、因數分解練習以及建立因數樹，而一份快速的質數清單能讓這些任務都更有效率。程式設計師則將質數產生器視為基準練習題，以及雜湊表、虛擬隨機序列的基礎元件，同時也是像 Project Euler 這類網站上程式挑戰的常見題目；在這些場合中，前幾百萬個質數是常見的測試資料。
加密技術是最具重大影響的日常應用。RSA 等演算法仰賴於對兩個極大質數之乘積進行因數分解的實際困難度，而這正是加密流量、軟體簽章與數位憑證得以安全的原因。即使您只是為了單元測試或壓力測試而需要一組確定性的測試整數，質數清單也是一個乾淨的來源，因為根據定義，質數沒有更小的因數。在新分頁中開啟質數產生器，選擇符合您問題的模式，讓篩法負責處理運算，您就可以專注在這份清單的真正用途上。