素因数分解

数をその素数の構成要素に分解する仕組み

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。

考慮すべき重要なポイント

• すべての素因数分解は一意です — これはまさに算術の基本定理が保証していることです。 数がどのように分解されても、その素因数分解は常に同じ結果になります(因数を書く順序を除いて)。これが素因数分解が数論全体を通じてこれほど基本的な構成要素である理由です。
• 素因数分解は、手作業で最大公約数(GCF)や最小公倍数(LCM)を求める仕組みの背後にあります。 2つの数の素因数分解を直接比較すると、それらのGCF(共有される素因数を、共有される低い方の指数で)とLCM(すべての素因数を、高い方の指数で)が明らかになります — その具体的な比較についてはGCF/LCM計算機を参照してください。
• 大きな数を因数分解することは、桁数が増えるにつれて計算上はるかに難しくなり、これが一部の暗号方式の基盤となっています。 試し割り(ここで使われている方法)は、人が通常手で入力する範囲の数にはうまく機能しますが、数百桁の非常に大きな数を因数分解することは強力なコンピューターでも計算上実行不可能になることがあります — この難しさこそがRSA暗号の安全性の根底にあるものです。
• 素数はちょうど1つの素因数、つまりそれ自身の1乗を持ちます。 これが、この計算機の「この数は素数か」というチェックが分解プロセスから直接導かれる理由です — もし試し割りがその数自身の平方根より小さい因数を一度も見つけられなければ、その数はそれ自身以外の分解を持ちません。

よくある間違い

• 素因数分解を因数の完全なリストと混同すること。 12の因数は1、2、3、4、6、12ですが、その 素因数分解は2² × 3だけです — 素因数分解は素数の構成要素だけを保持し、均等に割り切れるすべ ての数を保持するわけではありません。
• 1を素数として扱うこと。 定義上、素数はちょうど2つの異なる約数(1とそれ自身)を持ちます — 1は1つしか持たないため、素数でも合成数でもなく、素因数分解に現れることはありません。
• 繰り返される素因数を見失うこと。 8の素因数分解は単なる「2」ではなく2³です — 素数が何回 割り切るかを忘れると、分解が実際に表す数が変わってしまいます。

知っておくと便利なこと

• 1つの数自体の因数ではなく、2つの数の最大公約数(GCF)や最小公倍数(LCM)が必要ですか? 最大公約数・最小公倍数計算機 は2つの数の素因数分解を直接比較します。
• 分数を最も簡単な形に簡略化していますか? 分数計算機 はこの計算機が見つける のと同じ共有の素因数を使用します。
• 代わりに非常に大きいまたは非常に小さい数を扱っていますか? 指数表記計算機 は標準表記と科学的表記を相互変換します。