質數判斷器

最後更新：2026-05-18

質數的定義

質數是大於 1 的自然數，且除了 1 和它本身之外，沒有其他正因數能整除它。

• 2 是質數：只能被 1 和 2 整除
• 7 是質數：只能被 1 和 7 整除
• 12 是合成數：可被 1、2、3、4、6、12 整除

前二十個質數為：

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71$

質數在數字增大時出現頻率下降，但永遠不會消失。歐幾里得在約西元前 300 年便已證明質數有無窮多個。

1 不是質數的原因

直觀上或許覺得 1 應該是質數，因為它只能被 1 和本身整除。然而現代定義要求恰好有兩個不同的正因數，而 1 只有一個（它自身）。

更深層的原因是維護算術基本定理：每個大於 1 的整數都能唯一地分解為質數的乘積。若 1 被視為質數，這個唯一性便會崩潰：

$12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 = \ldots$

因此，1 被稱為單位元，既非質數也非合成數。

試除法的原理

對於 1 到 1000 範圍內的整數，本工具採用試除法：測試能否被每個不超過 $\sqrt{1000} \approx 31.6$ 的質數整除。若 $n$ 沒有小於或等於其平方根的質因數，則 $n$ 本身是質數。

不超過 31 的質數為：2、3、5、7、11、13、17、19、23、29、31。測試這十一個值，就能判定 1 到 1000 之間任何整數的質性。

範例：97 的質性判定

除數	$97 \div d$	餘數
2	48.5	1
3	32.3…	1
5	19.4	2
7	13.857…	6

沒有不超過 $\sqrt{97} \approx 9.8$ 的質數能整除 97，因此 97 是質數。

範例：91 的質性判定

$91 \div 7 = 13 \text{，餘數為 } 0$

因為 7 能整除 91，所以 91 是合成數（即 $7 \times 13$），最小質因數為 7。

埃拉托斯特尼篩法

若想找出某個上限以內的所有質數，埃拉托斯特尼篩法比逐一試除更有效率：

1. 列出 2 到 $N$ 的所有整數。
2. 從 2 開始，劃掉所有 2 的倍數（4、6、8……）。
3. 移至下一個未劃掉的數（3），劃掉其倍數。
4. 重複此步驟直到 $\sqrt{N}$。

所有剩餘未劃掉的數均為質數。演算法時間複雜度為 $O(N \log \log N)$。

質數與密碼學

幾乎所有公開金鑰密碼系統都依賴一個根本的不對稱性：將兩個大質數相乘容易，但將乘積分解回那兩個質數極其困難。

RSA 加密（用於 HTTPS 和數位簽章）的運作方式：

1. 選取兩個大質數 $p$ 和 $q$（通常各為 1024 至 4096 位元）。
2. 計算 $n = p \times q$，並作為公鑰的一部分公開。
3. 攻擊者必須對 $n$ 進行質因數分解才能破解金鑰——以當前電腦的運算能力，所需時間遠超宇宙年齡。

這種單向函數是現代網際網路安全通訊的基石。

快速參考

數字	質數？	最小質因數
1	否（單位元）	—
2	是	2（本身）
4	否	2
17	是	17（本身）
49	否	7
97	是	97（本身）
100	否	2
997	是	997（本身）

常見問題（FAQ）

什麼是質數？

質數是大於 1 的自然數，且除了 1 和它本身之外沒有其他正因數。例如 2、3、5、7、11、13 都是質數，而 12 不是質數，因為它可以被 2、3、4、6 整除。每個大於 1 的整數，不是質數就是若干質數的乘積——這就是算術基本定理。

為什麼 1 不是質數？

質數的定義要求恰好有兩個不同的正因數：1 和本身。1 只有一個正因數（它自身），不符合此定義。若將 1 視為質數，則質因數分解將不再唯一：12 = 2² × 3 = 1 × 2² × 3 = 1² × 2² × 3……會產生無數種分解方式。

前十個質數是什麼？

前十個質數為：2、3、5、7、11、13、17、19、23、29。2 是唯一的偶質數，其餘偶數均可被 2 整除，因此不是質數。歐幾里得在約西元前 300 年就已證明質數有無窮多個。

質數為何在密碼學中如此重要？

大多數公開金鑰密碼系統——包括保護 HTTPS 和數位簽章的 RSA——都依賴一個非對稱性：將兩個大質數相乘很容易，但將乘積分解回原來的質數卻極為困難。現代 RSA 金鑰使用數百位數的質數，正是這種難度保護了網際網路上的加密通訊。