素因数分解のやり方

素因数分解は、整数を素数だけの積の形に書き直すことです。2 以上のどんな整数も、掛ける順序を除けばただ 1 通りに素数の積へ分解できます。これを素因数分解の一意性（算術の基本定理）といいます。

この電卓は試し割りで求めます。2 で割れるだけ割り、次に 3 で割れるだけ割り、と小さいほうから順に試します。割る数の 2 乗が残りの数を超えたら、そこで打ち切ります。残った数が 1 より大きければ、それ自身が素因数です。

• $n$ — 分解したい整数。2 以上の整数を入れます
• 出力の「素因数分解」— 素因数を小さい順に並べた積
• 出力の「素因数の個数」— 同じ素数の重複も数えた個数です

例

$n = 360$ を分解します。

• $360 \div 2 = 180$、$180 \div 2 = 90$、$90 \div 2 = 45$ で、2 では 3 回割れます
• $45 \div 3 = 15$、$15 \div 3 = 5$ で、3 では 2 回割れます
• 残った 5 は素数です

したがって $360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5$、指数を使えば次のように書けます。

素因数の個数は、重複を含めて 6 個です。

注意

• 1 は素数でも合成数でもないので、入力は 2 以上にします
• 素因数が 1 個だけなら、その数自身が素数です。たとえば 97 の素因数分解は 97 の 1 個だけです
• 個数は「異なる素数の種類の数」ではなく「重複を含めた個数」です。360 なら 2 が 3 個、3 が 2 個、5 が 1 個で、合わせて 6 個です
• 試し割りは大きな数ほど時間がかかるため、この電卓では $10^{12}$ までに制限しています