質數是大於 1 的整數，恰好有兩個相異的正因數：1 與自身。這個數列從 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 開始，一直延續下去，其中 2 是唯一的偶質數，而 1 則被明確排除在外，因為它只有一個因數。若要產生一份到指定上限為止的完整質數清單，或依序取出前 N 個質數，你可以使用免費的質數產生器（Prime Number Generator），它完全在你的瀏覽器中執行經典的埃拉托斯特尼篩法（Sieve of Eratosthenes），並印出完整清單，連同數量、總和與最大質數。這種篩法從 2 開始的整數往上算，先劃掉 2 的倍數，再劃掉 3 的倍數，接著是 5 的倍數，依此類推；凡是撐過整個過程沒被劃掉的數，就沒有更小的因數，因此就是質數。正是這一個簡單的想法，把一項枯燥的紙筆練習變成了瞬間完成的運算。
什麼樣的數才算是質數
教科書上的定義簡短而明確。質數是大於 1 的正整數，其因數只有 1 與該數本身。依照這個規則，2 是質數，因為它的因數只有 1 與 2；3 是質數；4 不是，因為 1、2 與 4 都能整除它；9 也不是，因為 1、3 與 9 都能整除它。有兩個特殊情況值得留意。數字 1 只有一個因數，所以它不是質數；數字 0 也不是質數。數字 2 是最小的質數，也是唯一的偶質數，因為其他每個偶數都能被 2 整除，因此都是合數。
你可以照著同樣的方法一路檢驗下去，但一旦超過幾十個數，用手算就會很快變得乏味。質數產生器把同樣的想法機械化地套用，讓你能夠檢驗很大的範圍，並重現已知的清單，而不必動手寫下任何東西。
用來找出質數的方法
幾乎所有實務情況都可以用兩個概念涵蓋：試除法與篩法。試除法會用每一個較小的質數去除每一個候選整數；如果沒有任何一個能整除，這個數就是質數。埃拉托斯特尼篩法則反過來，一次處理整個範圍，逐一劃掉每個質數的倍數。
| 方法 | 運作方式 | 列出質數的速度 | 最適合的情境 |
|---|---|---|---|
| 試除法 | 用較小的質數逐一去除每個候選數來測試 | 當 N 很大時速度慢；每個數都得重新檢查一次 | 檢查單一個數是否為質數 |
| 埃拉托斯特尼篩法 | 在整個範圍內劃掉每個質數的倍數 | 大約是 O(n log log n)；能在不到一秒的時間內列出數百萬個 | 產生到 N 為止的完整質數清單 |
質數產生器所使用的正是埃拉托斯特尼篩法。從整數 2、3、4、5……一路到你指定的 N 開始，這個演算法會先劃掉每一個 2 的倍數，再劃掉每一個 3 的倍數，然後是 5 的倍數，依此類推。整趟過程結束後留下來的數，就沒有更小的因數，也就是質數。這種單一遍歷的方式比逐一測試每個數快得多，這也是為什麼這個工具能輕鬆處理到數百萬範圍而不費力。
用質數產生器產生質數清單
一旦你了解篩法在做什麼，使用這個工具就很直覺。打開頁面、選擇符合你目標的模式、輸入一個數字，然後閱讀結果。整個運算都在你的瀏覽器中完成，因此不會上傳任何內容，也沒有排隊等候。
- 選擇一種模式。選擇「到 N 為止的質數」可列出所有小於或等於某個上限的質數，或選擇「前 N 個質數」可依序取得恰好前 N 個質數。
- 輸入你的 N 值並執行。在輸入框中輸入上限或數量，然後點擊「產生質數」，或直接按下 Enter 鍵。
- 閱讀質數清單以及統計總數。清單下方會顯示總數量、找到的所有質數的總和，以及結果中最大的質數。
無論你要的是到 100 為止的質數，還是前一千個質數，同樣的三個步驟都適用；差別只在於 N 的大小。即使 N 非常大，頁面也會在你把手指從 Enter 鍵上抬起之前就完成運算。
解讀輸出結果：數量、總和與最大質數
清單只是答案的一部分。這個工具還會回報三個摘要數字，讓你能對原始輸出做個合理性檢查。數量告訴你實際取回了多少個質數。總和把清單中的每個質數加總起來。最大質數則是結果中產生的最大值，當你要求「到 N 為止的質數」並想知道結果究竟停在哪裡時，這個數字很有用。
為了說明格式，以「到 N 為止的質數」模式、N = 30 為例。回傳的質數是 2、3、5、7、11、13、17、19、23 與 29，數量為 10。一步一步用手加總：2 + 3 = 5，5 + 5 = 10，10 + 7 = 17，17 + 11 = 28，28 + 13 = 41，41 + 17 = 58，58 + 19 = 77，77 + 23 = 100，100 + 29 = 129，所以總和是 129。最大的質數是 29。這些數字符合「到 30 為止共有 10 個質數」的規則，如果你想驗證一次小範圍的執行結果，這正好可以作為快速的交叉檢查。
質數會出現在哪些地方
質數出現的場合，遠比數學教科書要多。老師與學生會用它們來上數論課、練習因數分解與畫因數樹。程式設計師則把質數產生器當作效能基準測試、雜湊表與偽隨機序列的建構元件，以及像 Project Euler 這類網站上程式挑戰題的素材。然而，最具份量的應用是密碼學：像 RSA 這樣的演算法，就仰賴兩個大質數的乘積很難被分解，而這種困難度正是加密資料得以保持安全的原因。
隨著數字變大，質數也會逐漸變得稀疏。質數定理指出，小於 n 的質數個數大約是 n 除以 n 的自然對數，因此密度會持續下降，儘管質數其實永遠不會用盡。像 11 與 13、或 17 與 19 這樣的孿生質數，正因如此才會持續出現；這種型態是緩慢淡去，而不是戛然而止。如果你的興趣正好相反，需要把一個數拆解成質數，而不是產生一份清單，質因數分解指南會帶你了解這枚硬幣的另一面。
檢查質數清單時方便對照的參考值
在信任任何輸出結果之前，先知道幾個參考點會很有幫助。下表中的數字直接取自眾所周知的清單，讓你能拿工具給出的結果，跟教科書上的說法互相比對。
| 里程碑 | 數值 |
|---|---|
| 小於 100 的質數 | 25 個質數（最大的是 97） |
| 到 30 為止的質數 | 10 個質數 |
| 第 25 個質數 | 97 |
| 第 100 個質數 | 541 |
| 第 1,000 個質數 | 7,919 |
| 第 10,000 個質數 | 104,729 |
| 第 100,000 個質數 | 1,299,709 |
你可以用質數產生器重現以上任何一項結果。要求前 25 個質數，清單應該以 97 結尾；要求前 100 個，應該以 541 結尾。如果工具給出的是別的結果，就表示某個地方出錯了。
需要留意的限制
即使是速度很快的瀏覽器篩法，也總得有個停止的地方。在「到 N 為止的質數」模式中，這個工具接受最高到 N = 10,000,000 的任何上限，遠遠超過大多數作業或程式設計題目所需要的範圍。在「前 N 個質數」模式中，上限是 N = 100,000 個質數，也就是說你能取到的最大值，是第 100,000 個質數，也就是 1,299,709。更大的輸入會被擋下，以確保頁面維持反應靈敏。一切都在你的瀏覽器本機執行，因此不需要上傳、不需要排隊，也沒有伺服器端對每個工作階段能列出多少質數所做的節流限制。
結合篩法 O(n log log n) 的速度、本機執行，以及相當寬裕的上限，質數產生器幾乎能涵蓋學生、程式設計師或好奇的讀者可能需要的任何清單。如果需要更大的範圍，標準做法是改用你所選語言中專屬的篩法實作，這也是從內部徹底學會這個演算法的絕佳方式。