質因數分解
求任意數字的質因數和約數
如何使用質因數分解
- 1輸入一個大於 1 的正整數。
- 2執行計算器將其分解為質因數。
- 3檢視帶指數的質數列表，例如 360 = 2³ × 3² × 5。
質因數分解詳解
n = p1^a1 × p2^a2 × ...（每個 p 為質數）質因數分解把數表示為質數的乘積，質數是大於 1 的每個整數的唯一構造單元。
它是求最大公約數、最小公倍數、密碼學以及判斷質數或完全冪的基礎。
算術基本定理保證：**每個大於 1 的整數都能唯一分解為質因數的乘積**（不考慮順序）。這個「唯一性」看似理所當然，實則是數論的基石——它保證了分數約分的結果唯一、GCD 和 LCM 的計算有確定答案。如果分解不唯一，整個初等數論都會崩塌。
實用的分解方法是「試除法」：從最小的質數 2 開始除，除不盡就試 3、5、7…，每次除到不能再除為止。關鍵最佳化是**只需要試到 √n**——如果 n 有大於 √n 的因數，那它必然配對一個小於 √n 的因數，早就試過了。例如分解 97，只需試到 √97 ≈ 9.8，即試 2、3、5、7 都不行，就能斷定 97 是質數。這個最佳化讓大數分解的耗時大幅下降。
| 數字 | 質因數分解 | 質因數個數 | 是否為質數 |
|---|---|---|---|
| 12 | 2² × 3 | 2 種 | 否 |
| 60 | 2² × 3 × 5 | 3 種 | 否 |
| 100 | 2² × 5² | 2 種 | 否 |
| 360 | 2³ × 3² × 5 | 3 種 | 否 |
| 1,001 | 7 × 11 × 13 | 3 種 | 否 |
| 97 | 97 | — | 是 |
常見數字的質因數分解
常見問題
為何是唯一的？
算術基本定理指出每個整數的質因數分解恰好只有一種。
1 呢？
1 不是質數，也沒有質因數；分解從 2 開始。
能處理多大的數？
試除法在百萬級以內沒問題；極大數需要高階演算法。
1 是質數嗎？
不是。質數的定義是「大於 1 且只能被 1 和自身整除的自然數」，1 被明確排除在外。排除 1 的原因正是為了保證分解的唯一性——如果允許 1 作為質因數，12 就可以寫成 2²×3、1×2²×3、1²×2²×3…，無限多種「分解」，算術基本定理就失效了。這是數學定義為了保持理論自洽而做的選擇。
大數分解為什麼是密碼學的基礎？
因為分解極其困難。把兩個大質數相乘很容易（計算機瞬間完成），但反過來把乘積分解回兩個質數，對幾百位的數來說，即使用最快的演算法和超級計算機也需要數千年。RSA 加密正是利用這種「單向性」：公鑰是兩個大質數的乘積（公開），私鑰是這兩個質數（保密）。目前量子計算機的 Shor 算法理論上能快速分解大數，這也是後量子密碼學研究的原因。