素因数分解計算機

この計算機の仕組み

1より大きいすべての整数は、掛け合わされる一意の素数の集合に分解できます — それがその数の素因数分解です。 整数を入力すると、この計算機はその素因数分解を即座に求め、さらにその数自体が素数かどうかも示します。

計算式

算術の基本定理は、1より大きいすべての整数Nが、因数を書く順序を除いてちょうど1つの素因数分解を持つことを保証します:

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

ここで各$\vB{p_i}$は異なる素数であり、各$\vC{a_i}$はその素数がNを何回割り切るかです。

この計算機は試し割りを使ってその分解を求めます: 2から始めて、各数が残りの値を割り切るかを繰り返し確認し、割り切るたびにそれを割り出し(何回割り切ったかを数え)、次の候補に移ります。ある候補の平方が残っている値を超えたら、まだ残っているものはそれ自体が素数でなければなりません — それより小さい因数はすでに見つかっているはずだからです:

$$\text{もし } \vD{d}^2 > \vE{\text{残りの値}}, \text{ ならば } \vE{\text{残りの値}} \text{ は素数です}$$

計算例

360の素因数分解を求める場合:

1. 360 ÷ 2 = 180、÷ 2 = 90、÷ 2 = 45(2は3回割り切ります。45は奇数なので次に進みます)。
2. 45 ÷ 3 = 15、÷ 3 = 5(3は2回割り切ります。5は3で再び割り切れません)。
3. 5が残り、それ以上の約数の平方は5以下にならないため、5自体が素数です。
4. 結果: 2³ × 3² × 5。