素因数分解とは?
素因数分解とは、整数を「掛け合わせると元の数になる素数の集まり」に分解する操作のことです。素数とは、1より大きく、約数が1とその数自身だけである数を指します(2、3、5、7、11…)。算術の基本定理によって、1より大きいすべての整数は、並べる順序の違いを除けば、ただ一通りの素因数分解を持つことが保証されています。
この計算機の使い方
2以上の整数を入力して「計算」を押すだけです。結果は2つの形式で表示されます。1つは素数をすべて個別に並べた「展開形」、もう1つは同じ素数を累乗としてまとめた「指数形」です。さらに、異なる素数がいくつ現れるか、重複を含めた素因数の総数、そしてその数自体が素数かどうかも合わせて確認できます。
計算の仕組み
この計算機は試し割り法を使っています。最小の素数である2から始めて、割り切れる間は候補となる約数dで繰り返し割り、それぞれが何回割り切れるかを数えます。約数を調べる範囲は\(\sqrt{n}\)までで十分です。平方根より小さい範囲に約数が見つからなければ、残った数はそれ自体が素数だからです。結果は次の形で表されます。
$$n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$
具体例で確認
\(n = 360\) を例にとってみましょう。まず2で3回割ります:\(360 \to 180 \to 90 \to 45\)(\(2^3\))。次に3で2回割ります:\(45 \to 15 \to 5\)(\(3^2\))。最後に5で1回割ります:\(5 \to 1\)(\(5^1\))。したがって $$360 = 2^3 \times 3^2 \times 5$$ です。展開すると \(2 \times 2 \times 2 \times 3 \times 3 \times 5\) となり、異なる素数は3種類、素因数の総数は6個になります。
素数と素因数分解の参考表
素数とは、1より大きい整数で、正の約数が1とその数自身だけのものです。100未満の素数はちょうど25個あります。1は素数でも合成数でもなく、2は唯一の偶数の素数です。
| 範囲 | 素数 | 個数 |
|---|---|---|
| 1–9 | 2, 3, 5, 7 | 4 |
| 10–19 | 11, 13, 17, 19 | 4 |
| 20–29 | 23, 29 | 2 |
| 30–39 | 31, 37 | 2 |
| 40–49 | 41, 43, 47 | 3 |
| 50–59 | 53, 59 | 2 |
| 60–69 | 61, 67 | 2 |
| 70–79 | 71, 73, 79 | 3 |
| 80–89 | 83, 89 | 2 |
| 90–99 | 97 | 1 |
よく使われる数の素因数分解(指数表記):
| 数 | 素因数分解 | 約数の個数 |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 24 | 2³ × 3 | 8 |
| 36 | 2² × 3² | 9 |
| 48 | 2⁴ × 3 | 10 |
| 60 | 2² × 3 × 5 | 12 |
| 100 | 2² × 5² | 9 |
| 120 | 2³ × 3 × 5 | 16 |
| 144 | 2⁴ × 3² | 15 |
| 210 | 2 × 3 × 5 × 7 | 16 |
| 360 | 2³ × 3² × 5 | 24 |
| 1000 | 2³ × 5³ | 16 |
| 1024 | 2¹⁰ | 11 |
結果の解釈
指数表記 \(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}\) は、相異なる各素数 \(p_i\) が \(n\) を何回割り切るかを示します。
- 約数の個数:\((a_1+1)(a_2+1)\cdots(a_k+1)\) に等しくなります。\(360 = 2^3 \times 3^2 \times 5\) の場合、\((3+1)(2+1)(1+1) = 24\) 個の約数があります。
- 素数判定:指数が1の素数が1つだけであれば、その数は素数であり、約数は1とその数自身だけです。
- 完全平方数:すべての指数が偶数であれば、その数は完全平方数です。\(144 = 2^4 \times 3^2\) の場合、指数を半分にすると \(2^2 \times 3 = 12\) となり、\(\sqrt{144} = 12\) です。
- 最大公約数と最小公倍数:最大公約数では共通する各素数を小さい方の指数で、最小公倍数ではすべての素数を大きい方の指数で取ります。\(360 = 2^3 \times 3^2 \times 5\) と \(84 = 2^2 \times 3 \times 7\) の場合、最大公約数 = \(2^2 \times 3 = 12\)、最小公倍数 = \(2^3 \times 3^2 \times 5 \times 7 = 2520\) です。確認:\(12 \times 2520 = 30240 = 360 \times 84\)。
- 分数の約分:分子と分母を最大公約数で割ります。\(\frac{84}{360} = \frac{84 \div 12}{360 \div 12} = \frac{7}{30}\)。
大きな数。2つの大きな素数を掛け合わせるのは容易ですが、その積(準素数)から素数を復元することは、古典的なコンピュータでは非常に困難だと考えられています。試し割り法は、数が数百桁に達するずっと前に実用的でなくなります。RSA暗号はこの非対称性に依存しており、2048ビット以上の法を使用します。なお、1は素因数を持たず、0は素因数分解を持たないことに注意してください。
よくある質問
なぜ2以上の数でなければならないのですか? 0と1には素因数分解が存在しません。特に1は素数でも合成数でもありません。
「重複を含めた」とはどういう意味ですか? 各素数が現れた回数だけ数えるという意味です。360の場合、2が3個、3が2個、5が1個で、合計6個になります。
1は素数ですか? いいえ。素数の定義では、ちょうど2つの異なる正の約数を持つ必要がありますが、1は約数が1つしかありません。