埃拉托斯特尼篩法生成器（免費）- 質數一覽・第N個質數查詢

只需輸入上限N，即可使用埃拉托斯特尼篩法逐步視覺化生成質數一覽。除1至100早見表外，還支援最大100萬範圍及第100萬個質數等大序數的反向查詢，免費、無需註冊、瀏覽器內直接計算。

1〜100 的埃拉托斯特尼篩法（一覽表）

綠色格子為質數，其餘為被篩法排除的合數。

1 既不是質數也不是合數，因此不上色。

這是相傳由西元前3世紀數學家埃拉托斯特尼提出的質數判定法：從 2 開始依次排列整數，機械地劃掉已發現質數的倍數，剩下的數便全部是質數。由於只需重複簡單操作，也非常適合用計算機實現。

由於本工具在瀏覽器內完成全部計算，上限設為最多 1,000,000。超出該範圍會大幅增加計算量，可能導致瀏覽器執行變慢。

根據質數定理估算第 N 個質數的大致上限，再在該範圍內執行埃拉托斯特尼篩法精確求出。支援最多查詢到第 1,000,000 個質數。

當結果數量較多時，只顯示前 1,000 個，其餘僅彙總顯示個數。逐步篩除過程的視覺化僅在上限為 400 以下時提供。

埃拉托斯特尼篩法是現存最古老的質數生成演算法之一，相傳由西元前3世紀擔任亞歷山大圖書館館長的古希臘學者埃拉托斯特尼所創。兩千多年前發明的方法至今仍作為電腦科學的教材使用，足見這一演算法的簡潔與優美。

篩法的原理出人意料地簡單：從 2 開始依次排列整數，將尚未被劃掉的最小數確定為質數，再劃掉它的所有倍數。只需將這一操作重複到 √N，即可得到 N 以內的全部質數。相比逐一判斷單個數字是否為質數的試除法，若要一次性求出一覽表，篩法效率高得多。

尋找巨大質數的競賽至今仍在繼續，GIMPS（網際網路梅森素數大搜索）等分散式計算專案不斷發現位數超過千萬位的梅森素數。埃拉托斯特尼篩法本身並不用於發現如此巨大的質數，但其基本思想（機械地排除倍數）也是更高階的質數判定演算法的基礎。