質數判斷器（免費）- 支援1000位、含質因數分解

輸入最多 1000 位的數字即可立即判斷是否為質數。同時顯示質因數分解、前後相鄰的質數、試除法步驟，以及本次結論由哪種判定法得出。免費、無需註冊。

1000 以內的全部 168 個質數

2 3 5 7 11 13 17 19 23 29 31 37
41 43 47 53 59 61 67 71 73 79 83 89
97 101 103 107 109 113 127 131 137 139 149 151
157 163 167 173 179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359
367 373 379 383 389 397 401 409 419 421 431 433
439 443 449 457 461 463 467 479 487 491 499 503
509 521 523 541 547 557 563 569 571 577 587 593
599 601 607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733 739 743
751 757 761 769 773 787 797 809 811 821 823 827
829 839 853 857 859 863 877 881 883 887 907 911
919 929 937 941 947 953 967 971 977 983 991 997

1000 以內其餘的數都是合數，即除了 1 和自身之外至少還有一個約數。

每個 10 的冪以內有多少個質數？

範圍上限 質數個數 π(x) 質數所佔比例
10 4 40%
100 25 25%
1,000 168 16.8%
10⁴ 1,229 12.29%
10⁵ 9,592 9.59%
10⁶ 78,498 7.85%
10⁷ 664,579 6.65%
10⁸ 5,761,455 5.76%
10⁹ 50,847,534 5.08%
10¹⁰ 455,052,511 4.55%
10¹² 37,607,912,018 3.76%
10¹⁵ 29,844,570,422,669 2.98%

π(x) 是質數計數函式，表示不超過 x 的質數個數。這個比例會不斷變小（在 x 附近大約每 ln(x) 個數中有 1 個質數），但永遠不會變成零，因為質數有無窮多個。

Tips

  • 質數是指大於 1 的整數中，除了 1 和它本身以外沒有其他因數的數。這個數列從 2, 3, 5, 7, 11, 13, … 開始，並且永遠不會結束。
  • 最基礎的質數檢測方法是試除法：用 2 到 √N 之間的每個整數去除 N。之所以到 √N 就可以停下，是因為如果 N = a × b，那麼較小的那個因數一定不超過 √N。
  • 手算時也能很快排除大部分數字：除 2 以外的偶數、以 5 結尾的數、各位數字之和為 3 的倍數的數，都是合數。另外，大於 3 的質數一定是 6k − 1 或 6k + 1 的形式。
  • 對於很大的數字，試除法並不現實，計算機會改用米勒–拉賓檢驗和 Baillie–PSW 檢驗。本頁面實現了這兩種方法，因此即使貼上一個 1000 位的數字，也能在一秒內得到結論。
  • 1 不是質數，因為定義中要求「大於 1」。而 2 是唯一的偶質數，比它更大的偶數都能被 2 整除。

常見問題

最多 1000 位。小於 10¹² 的數使用試除法，小於 3,317,044,064,679,887,385,961,981 的數使用確定性的米勒–拉賓檢驗，更大的數則使用 Baillie–PSW 檢驗。質因數分解和相鄰質數搜尋的計算量遠大於質數判定，因此支援範圍會小一些。

對於大約超過 3.3 × 10²⁴ 的數，結論來自 Baillie–PSW 檢驗。它目前沒有已知反例，但也沒有證明。實際上密碼學庫同樣依賴這一檢驗，所以「機率質數」的結論極為可靠。另外，相反方向的結論毫無疑義：顯示為合數時，說明確實找到了見證數或因數，那就是一個證明。

因為質數的定義要求「大於 1 的整數」。排除 1 才能保持質因數分解的唯一性：如果把 1 也算作質數，6 就可以寫成 2 × 3、1 × 2 × 3、1 × 1 × 2 × 3 等無窮多種形式，算術基本定理便不再成立。

2 除了 1 和它本身之外沒有別的因數，符合定義。它同時也是唯一的偶質數，因為比 2 更大的偶數都能被 2 整除，從而多出第三個因數。

不存在。西元前 300 年左右歐幾里得就證明了質數有無窮多個：把任意有限個質數相乘再加 1，所得的數一定含有不在這個列表中的質因數。存在的只是「目前已知最大的質數」，而這個紀錄一直在被打破，當前是 2024 年發現的 2¹³⁶²⁷⁹⁸⁴¹ − 1。

用不超過其平方根的質數依次去除即可：2, 3, 5, 7, 11, … 例如 391，√391 ≈ 19.8，所以只需試 2, 3, 5, 7, 11, 13, 17, 19，其中 17 能整除，得到 391 = 17 × 23。各位數字之和為 3 的倍數就能被 3 整除，這類技巧也很有用。
ツールくん

閒話 ― 質數為何如此重要

質數常被稱為「算術的原子」。算術基本定理指出，任何大於 1 的整數都能唯一地寫成若干質數之積，也就是說質數是構成所有整數、且無法再拆分的基本零件。上面顯示的質因數分解之所以是唯一的，原因也在這裡：360 就是 2³ × 3² × 5，不存在其他寫法。

判定一個巨大的數是否為質數，與把它分解成質因數，是兩個完全不同的問題，這一區別的歷史值得一說。利用費馬小定理可以做快速判定，但存在一些合數無論換哪個底都能矇混過關，其中最小的一個是 561，可以用上面的按鈕試一下（這類數稱為卡邁克爾數）。米勒–拉賓檢驗通過在中途檢查 1 的平方根堵住了這個漏洞，並且已經證明：以最前面的 13 個質數為底時，它對約 3.3 × 10²⁴ 以下的所有數都是確定性的判定法。超出這個範圍後，本頁面會加上強 Lucas 檢驗，構成 Baillie–PSW 檢驗。至今沒有發現任何能通過它的合數，但這一點尚未被證明，所以對非常大的數，結果會標註為「機率質數」。

正是這種「容易判定、難以分解」的不對稱性支撐起了現代密碼技術。至今仍在保護 HTTPS 通訊與數字簽名的 RSA 加密，就是把兩個大質數相乘來生成公鑰。人們相信從這個乘積還原出原來的兩個質數在計算上是不可行的，於是就形成了「驗證只需一瞬、分解卻做不到」的局面。這種差距在本頁面上也能親身體會：1000 位數字的質數判定幾乎瞬間完成，而兩個 30 位質數相乘得到的 60 位合數，卻分解不出來。

質數還留下了數學中最古老的一些未解難題。像 11 與 13，或者 1,000,000,000,061 與 1,000,000,000,063 這樣的孿生質數是否有無窮多對，至今無人知曉——儘管質數本身不會用盡這件事，早在西元前 300 年左右就被歐幾里得證明了。重新整理紀錄的搜尋也仍在繼續：GIMPS 專案的志願者們分頭檢驗形如 2^p − 1 的梅森數，目前已知最大的質數是 2024 年發現的 2¹³⁶²⁷⁹⁸⁴¹ − 1，共有 41,024,320 位。

閱讀相關趣味知識

檢視全部趣味知識

檢視此工具的人也看了

埃拉托斯特尼篩法生成器（免費）- 質數一覽・第N個質數查詢

只需輸入上限N，即可使用埃拉托斯特尼篩法逐步視覺化生成質數一覽。除1至100早見表外，還支援最大100萬範圍及第100萬個質數等大序數的反向查詢，免費、無需註冊、瀏覽器內直接計算。

質因數分解計算器（免費線上工具，2至1,000,000）

免費線上工具，立即將任意整數 N（2〜1,000,000）分解為質因數。顯示逐步除法過程、因數列表、因數個數及因數和。附1〜100質因數分解速查表。

最大公約數・最小公倍數計算器

輸入兩個正整數後，用輾轉相除法（歐幾里得演算法）求出最大公約數（GCD），並逐步顯示計算過程。同時計算出最小公倍數（LCM）。

模運算計算器（Mod 計算器）

支援4種模式的模運算計算器：基本mod、模加減乘運算、模冪運算（快速冪/平方求冪法）、模逆元（擴充套件歐幾里得演算法）。使用 BigInt 精確處理負數取模和超大指數運算。

中國剩餘定理（CRT）計算器 — 求解一次同餘方程組

使用中國剩餘定理求解形如 x ≡ a₁ (mod n₁)、x ≡ a₂ (mod n₂)… 的同餘方程組。自動驗證各模數是否兩兩互素，並給出最小非負整數解與通解。

尤拉函式（φ函式）計算器

輸入整數 N（1〜1,000,000），立即計算1到N之間與N互質的整數個數（尤拉函式 φ(N)），並顯示質因數分解與計算公式。附帶1〜100的φ(n)速查表。