素因数分解計算機

素因数分解計算機とは？

素因数分解計算機は、整数を受け取り、それを素数の積として書き直します。素数とは、1 とそれ自身以外に約数を持たない 1 より大きい整数のことで、2、3、5、7、11 などがあります。1 より大きいすべての整数は、素数であるか、または素数の一意な積として書くことができます。これは算術の基本定理として知られる結果です。この計算機はその分解を行い、因数を掛け算の記号でつないだ数字として表示します。例えば $60 = 2 \times 2 \times 3 \times 5$ です。

出力は数字と掛け算の記号だけなので、どの言語でも同じように読めます。

どのように機能しますか？

この計算機は、最も直接的な因数分解の方法である試し割りを使用します。最小の素数から始めて、割り切れる限り各候補の約数で数を繰り返し割り、その後次の候補に移ります。

1. 約数 $d = 2$ を設定します。
2. 数が $d$ で割り切れる間、$d$ を因数として記録し、数を $d$ で割ります。
3. $d$ を増やして繰り返します。約数はその数の平方根までテストすればよく、$d \times d$ が残りを超えた場合、残った値自体が素数だからです。
4. 最後に 1 より大きいものが残っていれば、それも素因数です。

数式で表すと、結果は積

$n = p_1 \times p_2 \times \cdots \times p_k$

となり、各 $p_i$ は素数であり、素数は小さいものから大きいものへと並べられ、繰り返しは明示的に示されます。

計算例

• 12 は 2 で割ると 6 になり、もう一度 2 で割ると素数である 3 になります。したがって $12 = 2 \times 2 \times 3$ です。
• 60 は 2 で割ると 30 になり、もう一度 2 で割ると 15、次に 3 で割ると素数である 5 になります。したがって $60 = 2 \times 2 \times 3 \times 5$ です。
• 17 はその平方根（約 4.12）までに約数がないため素数であり、分解は単に $17$ です。
• 100 は 2 で 2 回割ると 25 になり、次に 5 で 2 回割ると 1 になります。したがって $100 = 2 \times 2 \times 5 \times 5$ です。

実用上の注意

• 入力できる最小値は 2 です。0、1、負の数には素因数分解がないためです。1 を入力するか欄を空欄のままにすると、空の結果が返されます。
• 繰り返される因数は累乗としてではなく個別に列挙されるため、100 は $2^2 \times 5^2$ ではなく $2 \times 2 \times 5 \times 5$ として表示されます。
• 素因数分解は、2 つの数の最大公約数と最小公倍数を求めるための基礎です。最大公約数には両者が共有する素数を取り、最小公倍数にはすべての素数を組み合わせます。素数だけでなく、ある数のすべての約数を見るには、因数計算機を使用してください。