質因數分解計算機

最後更新：2026-05-19

質因數分解

每個大於 1 的整數都可以寫成質數的乘積，這種表示法稱為質因數分解。例如：

$360 = 2^3 \cdot 3^2 \cdot 5$

質數 2、3、5 是 360 的「原子」——它們無法再被進一步分解。指數（3、2、1）表示每個質數在乘積中出現的次數。

算術基本定理

算術基本定理保證了兩件事：

1. 存在性： 每個大於 1 的整數至少有一個質因數分解。
2. 唯一性： 除了因數的排列順序外，這個分解方式是唯一的。

為什麼 1 不是質數？ 如果 1 是質數，同一個數就會有無限多種分解方式（360 = 1 · 2³ · 3² · 5 = 1² · 2³ · 3² · 5 … 等等）。將 1 排除在質數之外，正是為了保持唯一性。

試除法的步驟

最直接的質因數分解方法是試除法：依序測試從 2 到 $\sqrt{n}$ 的所有整數是否能整除 n。

以 n = 360 為例：

1. 能被 2 整除嗎？能：360 ÷ 2 = 180，180 ÷ 2 = 90，90 ÷ 2 = 45。45 是奇數，不再能被 2 整除。確定因數 2³。
2. 能被 3 整除嗎？能：45 ÷ 3 = 15，15 ÷ 3 = 5。5 不能被 3 整除。確定因數 3²。
3. 能被 5 整除嗎？能：5 ÷ 5 = 1。確定因數 5¹。
4. 商為 1，分解完成。結果：$360 = 2^3 \cdot 3^2 \cdot 5$。

為何只需測試到 $\sqrt{n}$？ 若 n 有一個質因數 p > $\sqrt{n}$，則 n/p < $\sqrt{n}$，代表必有一個更小的因數存在。如果測試到 $\sqrt{n}$ 都找不到因數，則 n 本身就是質數。

因數樹

因數樹是一種視覺化方法：將一個數分解成任意兩個因數，重複此步驟，直到所有分支都以質數結尾。

         360
        /    \
       8      45
      / \    /  \
     4   2  9    5
    / \    / \
   2   2  3   3

葉節點為 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5。不管如何分支，最終結果都相同——這正是唯一性的具體體現。

從質因數分解計算因數個數

知道質因數分解後，正因數的總數可以用一個公式計算：

$\tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$

為什麼是這個公式？ n 的每個因數都是透過獨立選擇每個質數 $p_i$ 的指數（從 0 到 $e_i$）所形成的——每個質數有 $(e_i+1)$ 種選法，各質數的選法彼此獨立，因此相乘。

360 的因數個數：

$\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$

360 恰好有 24 個正因數。

從質因數分解求最大公因數與最小公倍數

知道兩個數的質因數分解，就能直接讀出它們的最大公因數（GCD）與最小公倍數（LCM）：

• 最大公因數（GCD）： 取每個質數的最小指數。
• 最小公倍數（LCM）： 取每個質數的最大指數。

例：360 與 504 的 GCD 與 LCM

$360 = 2^3 \cdot 3^2 \cdot 5, \qquad 504 = 2^3 \cdot 3^2 \cdot 7$

質數	360 的指數	504 的指數	最小 (GCD)	最大 (LCM)
2	3	3	3	3
3	2	2	2	2
5	1	0	0	1
7	0	1	0	1

$\gcd(360, 504) = 2^3 \cdot 3^2 = 72, \qquad \text{lcm}(360, 504) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$

約分分數

將 $\dfrac{a}{b}$ 化為最簡分數時，將分子與分母同除以 $\gcd(a, b)$：

$\frac{360}{504} = \frac{360 \div 72}{504 \div 72} = \frac{5}{7}$

質因數分解的應用

領域	如何運用
密碼學（RSA）	安全性建立在分解兩個大質數之積的困難性上
雜湊表	質數大小能使碰撞更均勻分散
編碼理論	糾錯碼的生成多項式
音樂理論（純律）	音程比例是 2、3、5 的次方之比

特殊情況

• n = 2（最小的質數）： 分解就是 2 本身；恰好有 2 個因數。
• n 是質數： 只有一個質因數；因數個數 = 2。
• n 是質數的次方（如 1024 = 2¹⁰）： 只有一個不同質因數；因數個數 = 11。
• 高度合成數（360、720、1260…）： 在同等大小的數中，因數最多。

快速參考

概念	公式
質因數分解	$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
相異質因數個數	$\omega(n) = k$
因數總數	$\tau(n) = \prod (e_i + 1)$
兩數的 GCD	取各質數的最小指數乘積
兩數的 LCM	取各質數的最大指數乘積
恆等式	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$

常見問題（FAQ）

什麼是質因數分解？

質因數分解是將一個大於 1 的整數表示為質數乘積的過程。例如 360 = 2³ · 3² · 5。算術基本定理保證這種表示方式除因數順序外是唯一的，是整除性、最大公因數與最小公倍數計算的基礎。

為什麼每個整數的質因數分解是唯一的？

算術基本定理指出，每個大於 1 的整數都恰好有一種質因數分解（不計因數的排列順序）。這種唯一性是定義最大公因數（GCD）與最小公倍數（LCM）不含糊的前提，也是 RSA 加密安全性的數學基礎。

如何從質因數分解求因數個數？

若 n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ，則正因數總數為 τ(n) = (e₁+1)(e₂+1)…(eₖ+1)。以 360 = 2³ · 3² · 5¹ 為例：τ(360) = 4 × 3 × 2 = 24，因此 360 恰好有 24 個正因數。

這個計算機最大能分解多大的數？

本計算機支援最大 1,000,000,000,000（10¹²，1 兆）的整數。採用試除法，只需測試 2 到 √n 的因數，最多約 100 萬次運算，在瀏覽器中執行速度很快。若需分解更大的數，則需使用 Pollard rho 演算法或二次篩選法等特殊方法。