什麼是質數?
質數是指大於 1,且只有兩個相異正因數(也就是 1 與它自己)的整數。常見的質數包括 2、3、5、7、11 與 13。至於大於 1 卻不是質數的數,則稱為「合數」,因為它們可以拆解成幾個較小整數的乘積。這個計算機會立刻告訴你輸入的數字是不是質數;如果不是,還會顯示能整除它的最小因數。
如何使用這個計算機
在輸入框中填入任何整數(0 或更大),然後送出。結果框會顯示 是 代表是質數,或顯示 否 代表是合數。當數字為合數時,表格還會列出大於 1 的最小因數,方便你接著進行完整的質因數分解。
公式原理說明
想要有效率地判斷質數,其實只需要測試到 \(n\) 的平方根為止的因數即可。原因在於:如果 \(n\) 有一個比平方根大的因數,那它必定也有一個比平方根小的對應因數,因此測試到平方根就已經足夠。用較嚴謹的方式來說,當 \(n > 1\),而且對於每個從 2 到 \(\lfloor\sqrt{n}\rfloor\) 的整數 \(i\),\(n \bmod i \neq 0\) 時,\(n\) 就是質數。相較於逐一測試小於 \(n\) 的每個數字,這種方法能大幅減少計算量。
$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$
實際範例
以 \(n = 97\) 為例。它的平方根約為 \(9.85\),所以我們只需測試 2、3、5、7 與 9。這些數都無法整除 97(97 是奇數,也不能被 3、5、7 整除),因此 97 是質數。再看 \(n = 91\),依序測試 2、3、5,接著測試 7 時會發現 \(91 \div 7 = 13\) 剛好整除,所以 91 是合數,最小因數為 7。
如何手動判斷一個數是否為質數
質數是大於 1 的整數,且其僅有的正因數為 1 和它本身。要檢驗整數 \(n\),只需檢查不大於 \(\lfloor\sqrt{n}\rfloor\) 的因數。若 \(n\) 有一個大於其平方根的因數,則它必定也有一個小於平方根的對應因數。
- 排除 \(n < 2\)。0、1 和負數都不是質數。
- 接受 2 和 3。兩者都是質數。2 是唯一的偶質數。
- 排除偶數。任何大於 2 的偶數 \(n\) 都能被 2 整除,因此它是合數。
- 計算 \(\lfloor\sqrt{n}\rfloor\)。找出平方不超過 \(n\) 的最大整數。例如,\(14^2 = 196 \le 221 < 225 = 15^2\),所以 \(\lfloor\sqrt{221}\rfloor = 14\)。
- 從 3 起檢驗奇數因數,或只檢驗質數,直到 \(\lfloor\sqrt{n}\rfloor\)。對每個候選數 \(d\),檢查 \(n \bmod d = 0\) 是否成立。可以使用下方的整除捷徑來加快速度。
- 作出判斷。若找到任何因數,則 \(n\) 是合數,而第一個被找到的因數就是它大於 1 的最小因數。若沒有任何數能整除 \(n\),則 \(n\) 是質數。
整除捷徑
- 被 3 整除:各位數字之和可被 3 整除。例如:51 的各位數字和為 5 + 1 = 6,所以 51 = 3 × 17。
- 被 5 整除:末位數字是 0 或 5。
- 被 11 整除:從右或從左開始,取各位數字的交錯和。若結果為 0 或 11 的倍數,則該數可被 11 整除。例如:121 的計算為 1 − 2 + 1 = 0,所以 121 = 11 × 11。
範例 1:221 是質數嗎?
- 221 ≥ 2,它是奇數,且不是 2 或 3。
- \(\lfloor\sqrt{221}\rfloor = 14\),因此檢驗質數 3、5、7、11 和 13。
- 3:各位數字和為 2 + 2 + 1 = 5,不能被 3 整除。
- 5:末位數字是 1,所以不行。
- 7:\(7 \times 31 = 217\),且 \(221 - 217 = 4\),有餘數,所以不行。
- 11:交錯和為 1 − 2 + 2 = 1,所以不行。
- 13:\(13 \times 17 = 221\),所以 13 能整除 221。
221 是合數,其最小因數為 13。
範例 2:97 是質數嗎?
- 97 是奇數,且大於 3。
- \(9^2 = 81 \le 97 < 100 = 10^2\),因此 \(\lfloor\sqrt{97}\rfloor = 9\)。檢驗 3、5 和 7。
- 3:各位數字和為 9 + 7 = 16,不能被 3 整除。
- 5:末位數字是 7,所以不行。
- 7:\(7 \times 13 = 91\),且 \(97 - 91 = 6\),有餘數,所以不行。
在 9 以內沒有任何數能整除 97,因此 97 是質數。
這種手動方法適用於小至中等的數字。對於非常大的數字,試除法會變得很慢,此時改用專門的質數判定測試。
計算慣例與邊界情況
以下每個情況都在本計算機上實際執行過,結果欄就是它真正回傳的值。
| 情況 | 輸入 | 結果 |
|---|---|---|
| 1 是質數嗎? | 1 | 否 |
| 2 是質數嗎? | 2 | 是 |
| 0 是質數嗎? | 0 | 否 |
核對於 2026-11-08
常見問題
1 是質數嗎? 不是。依照定義,質數必須大於 1,所以 1 既不是質數,也不是合數。
2 是質數嗎? 是的。2 是唯一的偶質數;其他所有偶數都能被 2 整除。
為什麼只要測試到平方根就好? 因為因數總是成對出現,兩兩相乘等於 \(n\)。如果一對因數都大於 \(\sqrt{n}\),它們的乘積就會超過 \(n\),這是不可能的——所以每一對因數中至少有一個會小於或等於 \(\sqrt{n}\)。