01
什麼是質數？
質數是大於 1 的自然數，除了 1 和本身之外沒有其他正因數。例：2、3、5、7、11、13…… 除了 2 以外，所有質數都是奇數。質數是「數字的原子」。
質數計算器
質數判定 · 因數分解 · 質數生成
瞭解更多
02
埃拉托色尼篩法
這是一種由希臘數學家埃拉托色尼在約西元前 240 年提出的古老演算法。它透過反覆標記每個質數的倍數為合數，能有效找出所有不大於 n 的質數。
03
孿生質數
孿生質數是相差 2 的質數對：(3,5)、(5,7)、(11,13)、(17,19)…… 是否存在無限多組孿生質數，至今仍是未解問題。
04
質數的應用
• RSA 加密：安全性建立在大數分解困難上 • 雜湊函式：使用質數大小的雜湊表可減少碰撞 • 隨機數生成：質數用於 PRNG 演算法 • 自然界：蟬的生命週期會使用質數
05
質數的定義與歷史
質數是大於 1 的自然數，除了 1 和本身之外沒有其他因數。最小的質數是 2，也是唯一的偶質數。數列：2、3、5、7、11、13、17、19、23、29…… 古希臘數學家歐幾里得約在西元前 300 年證明了質數有無限多個。質數被稱為「數字的原子」，因為每個大於 1 的整數都能唯一分解為質數乘積（算術基本定理）。例：60 = 2² × 3 × 5，360 = 2³ × 3² × 5。
06
質數判定演算法
最簡單的方法是測試從 2 到 n-1 的所有數是否可整除，但效率很差。改良方法只測試 2 到 √n，因為如果 n = a × b，則 a ≤ √n 或 b ≤ √n。以 101 為例：√101 ≈ 10.05，所以只要測 2、3、5、7。Miller-Rabin 機率式測試能有效處理非常大的數字。AKS（2002）是第一個多項式時間的確定性演算法。現代密碼學使用數百位數，因此需要高效率的測試。
07
埃拉托色尼篩法演算法
由希臘數學家埃拉托色尼於約西元前 240 年提出。步驟：① 列出 2 到 n 的所有數。② 標記 2 為質數，刪去其倍數（4、6、8、10……）。③ 下一個未標記的數 3 為質數，刪去其倍數。④ 持續對 5、7 等重複，直到 √n。⑤ 剩下的數即為質數。以 n=30 為例：質數為 2、3、5、7、11、13、17、19、23、29。時間複雜度：O(n log log n)。可在數秒內找出 1,000,000 以下的所有質數。
08
質因數分解原理
質因數分解是將一個數表示為質數的乘積。依據算術基本定理，每個大於 1 的整數都有唯一的分解方式。方法：① 從最小質數 2 開始。② 持續除以 2，直到不能整除。③ 再試 3、5、7…… 等下一個質數。④ 持續到商為 1。例：360：360÷2=180，180÷2=90，90÷2=45，45÷3=15，15÷3=5，5÷5=1。結果：360 = 2³×3²×5。應用：最大公因數／最小公倍數計算、分數約分、RSA 安全性。
09
孿生質數與哥德巴赫猜想
孿生質數相差 2：(3,5)、(5,7)、(11,13)、(17,19)、(29,31)…… 孿生質數猜想主張這樣的質數對有無限多組，但仍未被證明。2013 年，張益唐證明了無限多對質數的差不超過 70,000,000，之後又被降到 246。哥德巴赫猜想（1742）：每個大於 2 的偶數都可以表示為兩個質數之和。例：4=2+2、6=3+3、8=3+5、10=5+5。已驗證到 4×10¹⁸，但仍未被證明。
10
RSA 加密與實際應用
RSA 加密是網際網路安全的核心，它利用「乘法容易、質數大數分解困難」的特性。金鑰生成：① 選擇大質數 p、q（各至少 1024 位元）。② 計算 n = p×q（公開）。③ 計算 φ(n) = (p-1)(q-1)。④ 選擇與 φ(n) 互質的公鑰指數 e（通常為 65537）。⑤ 計算私鑰指數 d，使 e×d ≡ 1 (mod φ(n))。公鑰：(n,e)，私鑰：(n,d)。加密：C = M^e mod n，解密：M = C^d mod n。若能分解 n 找出 p、q，就能破解加密，但分解數百位數需要數百萬年。其他應用：使用質數大小的雜湊表可減少碰撞，蟬 13/17 年的週期可避免與天敵重疊，音樂中也有質數節奏。
常見問題
我可以測試的範圍是什麼？
這個工具支援 1 到 10,000,000 的質數判定與因數分解，而質數生成與孿生質數搜尋則適用於 2–100,000 的範圍。
為什麼密碼學會使用質數？
把兩個大質數相乘很容易，但要把乘積再分解回這兩個質數卻極其困難。RSA 加密正是利用這種不對稱性來保護網路通訊。