素因数分解の計算

最終更新: 2026-05-19

素因数分解とは

1 より大きいどの整数も、素数だけの積として表すことができます。この表現を素因数分解といいます。たとえば：

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

2、3、5 はいずれも素数（1 と自分自身以外に約数を持たない整数）であり、360 の「原子」にあたります。指数（3、2、1）はそれぞれの素数が積の中に何回現れるかを示しています。

算術の基本定理

算術の基本定理は、次の 2 つを保証します。

1. 存在性： 1 より大きい整数はかならず素因数分解できる。
2. 一意性： その表現は、因数の順序を除いてただ一通りである。

なぜ 1 は素数でないのでしょうか。もし 1 を素数とすると、360 = 2³ × 3² × 5 = 1 × 2³ × 3² × 5 = 1² × 2³ × 3² × 5 … と無限に異なる表現が生じてしまいます。一意性を守るために、1 は素数から除外されています。

この定理があるため、約数・公約数・公倍数など整数の性質はすべて「素数の指数の組み合わせ」として捉えることができます。

試し割り法の手順

素因数分解の最も基本的な方法は試し割り法です。2 から $\sqrt{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 に $\sqrt{n}$ より大きな素因数 p があるとすると、n/p < $\sqrt{n}$ となるため、$\sqrt{n}$ 以下の因数が必ず存在します。つまり $\sqrt{n}$ 以下に因数が見つからなければ、n 自体が素数です。

素因数の樹形図（素因数の木）

数を視覚的に分解する方法として素因数の木（factor tree）があります。任意の 2 数の積に分けることを、すべての葉が素数になるまで繰り返します。

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

葉を集めると 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5。どのように枝を分けても、最終的に同じ素因数分解が得られます（一意性の直感的な確認）。

約数の個数の求め方

素因数分解がわかれば、約数の総数を公式 1 つで求められます。

$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} \implies \tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$

なぜこの式か？ n の約数は、各素数 $p_i$ ごとに、指数として $e_i$ 以下の非負整数を独立に選ぶことで作られます。選択肢は $(e_i + 1)$ 通りあり、それらが独立なので掛け算になります。指数が 0 の場合は「その素数を含まない」約数に対応します。

360 の約数の個数：

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

360 の約数はちょうど 24 個（1、2、3、4、5、6、8、9、10、12、15、18、20、24、30、36、40、45、60、72、90、120、180、360）あります。

最大公約数・最小公倍数との関係

2 つの整数の素因数分解がわかれば、最大公約数（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 の指数	min（GCD）	max（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 つの大きな素数の積を因数分解することが困難なことを安全性の根拠にする
ハッシュテーブル	サイズを素数にすると衝突が均一に分散しやすい
音楽理論	純正調の音程比は 2・3・5 の累乗の積で表せる
カレンダー計算	2 つの周期の次の一致は LCM 日後（公倍数の問題）

特殊なケース

• n = 2（最小の素数）： 素因数分解は 2 のみ。約数は 1 と 2 の 2 個。
• n が素数： 素因数は n 自身のみ。約数は常に 2 個。
• n が完全乗（例：1024 = 2¹⁰）： 異なる素因数は 1 種類。約数の個数は指数 + 1 = 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 × LCM の恒等式	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$

よくある質問 (FAQ)

素因数分解とは何ですか？

素因数分解とは、1より大きい整数を素数だけの積で表すことです。たとえば 360 = 2³ × 3² × 5 です。算術の基本定理により、この表現は順序を除いて一意に定まります。つまりどのように分解しても、最終的に得られる素数と指数の組み合わせは必ず同じになります。

素因数分解はなぜ一通りしかないのですか？

算術の基本定理によって保証されています。1より大きい整数は素数の積として、因数の順序を除いてただ一通りにしか表せません。これにより整数は「素数の指数の組」として一意に識別でき、約数や公約数・公倍数の計算の基礎となっています。なお 1 は素数ではないため、この定理の適用外です。

素因数分解から約数の個数はどう求めますか？

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 個あります。各素数について 0 から eᵢ まで独立に指数を選べるため、掛け算で個数が出ます。

この計算機で扱える最大の数はいくつですか？

1,000,000,000,000（10¹²、1兆）まで対応しています。内部では √n 以下の整数で順番に割り切れるかを試す「試し割り法」を使っており、最大でも約100万回の繰り返しで完了するため、ブラウザ上でも実用的な範囲で計算できます。これより大きな数の素因数分解には、ポラード・ロー法や二次篩などの特殊なアルゴリズムが使われます。