什麼是質數?
質數(也稱為「素數」)是指大於 1,且只有兩個正因數(1 與本身)的整數。如果一個數字的因數超過兩個,就稱為合數。數字 1 比較特別:它只有一個因數,因此既不是質數,也不是合數。這個計算機會判斷你輸入的數字是質數還是合數、列出它的所有因數,並顯示前一個與下一個質數。
使用方法
在欄位中輸入一個大於 1 的整數後送出。工具會將它歸類為質數或合數、重新顯示該數字、列出所有因數(合數適用),並回報它下方最大的質數與上方最小的質數。
計算原理說明
我們採用具有 \(6k\pm1\) 最佳化的確定性試除法。首先把 2 與 3 視為已知質數,並排除偶數以及 3 的倍數。接著只測試形如 \(6k-1\) 與 \(6k+1\) 的候選因數(5、7、11、13……),測試範圍到 \(n\) 的平方根為止。如果都無法整除 \(n\),\(n\) 就是質數。判斷質數的條件可寫為:
$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$
之所以只需測試到平方根,是因為任何大於平方根的因數,必定會與一個小於平方根的因數成對出現。
實例演算
以 \(n = 97\) 為例,它的平方根大約是 \(9.85\)。它是奇數,也不是 3 的倍數。我們測試 5(\(97 \bmod 5 = 2\))與 7(\(97 \bmod 7 = 6\))。下一個候選數是 11,但 \(11 \times 11 = 121 > 97\),所以停止測試。由於找不到任何因數,因此 97 是質數。前一個質數是 89,下一個質數是 101。
質數與合數:範例輸入比較
下表顯示試除法測試如何處理七個輸入值。平方根上界為 \(\lfloor\sqrt{n}\rfloor\),也就是必須嘗試的最大除數。如果從 2 到該上界之間的任何整數都無法整除 \(n\),那麼 \(n\) 就是質數。前一個質數與後一個質數,分別是嚴格小於與嚴格大於 \(n\) 的最近質數。
| 輸入值 n | 狀態 | 所有因數 | 前一個質數 | 下一個質數 | 平方根上界 \(\lfloor\sqrt{n}\rfloor\) |
|---|---|---|---|---|---|
| 2 | 質數 | 1, 2 | 無 | 3 | 1(沒有需要嘗試的除數;2 是唯一的偶數質數) |
| 9 | 合數 | 1, 3, 9 | 7 | 11 | 3(3 可整除 9) |
| 15 | 合數 | 1, 3, 5, 15 | 13 | 17 | 3(3 可整除 15) |
| 49 | 合數 | 1, 7, 49 | 47 | 53 | 7(7 可整除 49) |
| 91 | 合數 | 1, 7, 13, 91 | 89 | 97 | 9(7 可整除 91) |
| 97 | 質數 | 1, 97 | 89 | 101 | 9(2、3、5、7、9 都無法整除 97) |
| 121 | 合數 | 1, 11, 121 | 113 | 127 | 11(11 可整除 121) |
看似質數的合數: 49、91 和 121 很容易被誤認為質數,因為它們是奇數,且不能被 3 或 5 整除。
- \(49 = 7 \times 7\)
- \(91 = 7 \times 13\)
- \(121 = 11 \times 11\)
每個數都有一個不大於其平方根上界的除數,因此如果只檢查 2、3 和 5,就會錯誤地判定它們為質數。相比之下,97 在 9 以內沒有任何除數,所以它是質數。
關鍵術語與定義
- 質數
- 大於 1 的整數,且其僅有的正除數為 1 與它本身(例如 2、3、5、7、97)。
- 合數
- 大於 1 的整數,且至少有一個除了 1 與它本身以外的除數(例如 9、49、91)。數字 0 與 1 既不是質數也不是合數。
- 因數/除數
- 能整除 \(n\) 且無餘數的整數 \(d\)。對 15 而言,其因數為 1、3、5、15。
- 模運算(mod)
- 除法後的餘數。\(n \bmod d = 0\) 表示 \(d\) 恰好整除 \(n\)。例如,\(91 \bmod 7 = 0\),但 \(97 \bmod 7 = 6\)。
- 平方根上界
- 若 \(n = a \times b\) 且 \(a \le b\),則 \(a \le \sqrt{n}\)。因此任何合數都有一個介於 2 與 \(\lfloor\sqrt{n}\rfloor\) 之間的除數,超過此範圍的測試是不必要的。
- 試除法
- 一種質數判定法,以 2 至 \(\lfloor\sqrt{n}\rfloor\) 之間的候選除數去除 \(n\)。若任一除法的餘數為 0,則 \(n\) 為合數;否則為質數。此法簡單可靠,對中等大小的數字而言速度也很快。
- 6k±1 形式
- 每個大於 3 的質數都可寫成 \(6k-1\) 或 \(6k+1\)(k 為某個整數),因為 mod 6 的其他餘數都可被 2 或 3 整除。這使測試能跳過約三分之二的候選除數。反之則不成立:25、35、49 和 91 也具有此形式,但它們是合數。
- 孿生質數
- 相差 2 的兩個質數,例如 (3, 5)、(11, 13)、(17, 19) 和 (41, 43)。是否存在無限多對孿生質數,是數學中尚未解決的問題。
計算慣例與邊界情況
以下每個情況都在本計算機上實際執行過,結果欄就是它真正回傳的值。
| 情況 | 輸入 | 結果 |
|---|---|---|
| 1 是質數嗎? | 1 | 既非質數也非合數 |
| 2 是質數嗎? | 2 | 質數 |
| 0 是質數嗎? | 0 | 無效 |
核對於 2026-11-08
常見問題
1 是質數嗎?不是。1 只有一個因數,所以它既不是質數,也不是合數。
2 是質數嗎?是的。2 是最小的質數,也是唯一的偶質數,它沒有前一個質數。
為什麼只有合數才列出因數?根據定義,質數的因數只有 1 與本身,因此工具只會直接說明這一點。合數可能有許多因數,會依照由小到大的順序列出。