埃拉托斯特尼篩法生成器（免費）- 質數一覽・第N個質數查詢
只需輸入上限N，即可使用埃拉托斯特尼篩法逐步視覺化生成質數一覽。除1至100早見表外，還支援最大100萬範圍及第100萬個質數等大序數的反向查詢，免費、無需註冊、瀏覽器內直接計算。
1〜100 的埃拉托斯特尼篩法（一覽表）
綠色格子為質數，其餘為被篩法排除的合數。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1 既不是質數也不是合數，因此不上色。
埃拉托斯特尼篩法是什麼
埃拉托斯特尼篩法是以西元前3世紀希臘學者埃拉托斯特尼命名的、用來尋找質數的古典演算法。思路出奇地單純：從2開始依序考察，凡是尚未被劃掉的數就確定為質數，然後把它的所有倍數劃掉。先劃掉2的倍數，再劃掉餘下的3的倍數，接著是5的倍數——把這套操作重複到上限的平方根為止，沒被劃掉的數就全是質數。
本工具只要指定上限 N，就能產生最多到100萬的質數一覽。由於會逐步顯示篩除過程，您可以親眼追蹤演算法「用哪個質數、劃掉了哪些數」。 此外還支援「第N個質數是什麼」的反查，連第100萬這樣靠後的名次也能查到。所有計算都在瀏覽器中完成，輸入的數值不會被傳送到任何地方。
產生質數一覽的步驟
- 輸入上限 N 指定2以上、1,000,000以下的整數。先用100之類的小值試試，篩法的機制會更清楚。
- 查看質數個數與最大質數 會顯示 N 以下共有多少質數（π(N)），以及 N 以下最大的質數。
- 跟隨篩除的步驟 上限較小時，會逐階段顯示使用了哪個質數、劃掉了哪些數。
- 反查第N個質數 輸入名次即可求出對應該名次的質數。
用好本工具的小技巧
- 埃拉托斯特尼篩法通過從 2 開始依次劃掉質數的倍數，能高效地列出 N 以內的全部質數。
- 將上限 N 設為 400 以下時，可以逐步確認是哪個質數篩掉了哪些數。
- 本工具支援「第1,000,000個質數是什麼」這類大序數的反向查詢，便於確認位數很大的質數是否存在。
- 生成的質數一覽完全在瀏覽器本地計算，不會向伺服器傳送任何資料。
這些情境會用到
學習演算法
作為 O(n log log n) 複雜度的代表例子，它必定出現在教科書裡。邊看實際執行邊理解更牢固。
驗證自己的程式實作
可以把自己寫的篩法輸出與本工具比對，確認是否給出正確的質數序列。
觀察質數的分布
改變上限並觀察 π(N) 的成長，能體會質數定理所說的「大致遵循 N / log N」的傾向。
為密碼學話題做功課
RSA 等公開金鑰密碼依賴大質數。這是掌握質數密度的一個入口。
質數與篩法的術語
- 質數
- 除1與自身外沒有其他正因數的、2以上的自然數。1不算質數。
- 合數
- 不是質數的、2以上的自然數。篩法中被劃掉的正是這些數。
- π(N)
- 表示 N 以下質數個數的函數，稱為質數計數函數。
- 篩除
- 給質數的倍數做記號並將其排除出候選的操作，演算法的名字正源於此。
- 為何到平方根即可
- 大於 N 平方根的質數的倍數，早已作為更小質數的倍數被劃掉了。
- 質數定理
- π(N) 漸近於 N / log N 的定理，描述了質數變得稀疏的速度。
常見問題
閒話 ― 為何2000年前的演算法至今仍在使用
埃拉托斯特尼篩法是現存最古老的質數生成演算法之一，相傳由西元前3世紀擔任亞歷山大圖書館館長的古希臘學者埃拉托斯特尼所創。兩千多年前發明的方法至今仍作為電腦科學的教材使用，足見這一演算法的簡潔與優美。
篩法的原理出人意料地簡單：從 2 開始依次排列整數，將尚未被劃掉的最小數確定為質數，再劃掉它的所有倍數。只需將這一操作重複到 √N，即可得到 N 以內的全部質數。相比逐一判斷單個數字是否為質數的試除法，若要一次性求出一覽表，篩法效率高得多。
尋找巨大質數的競賽至今仍在繼續，GIMPS（網際網路梅森素數大搜索）等分散式計算專案不斷發現位數超過千萬位的梅森素數。埃拉托斯特尼篩法本身並不用於發現如此巨大的質數，但其基本思想（機械地排除倍數）也是更高階的質數判定演算法的基礎。