素因数分解計算機

このオンライン因数分解計算機は、入力数のすべての素因数を見つけます。計算機は、一般形式、指数形式、CSV形式で素因数を示します。さらに、この因数分解計算機は素因数ツリーを作成し、指定された数のすべての (素数だけでなく) 因子を見つけることができます。

使用方法

この計算機を使用して数値の素因数を見つけるには、指定された数値を入力して “計算”を押します。計算機は、数値の素因数を一般形式、指数形式、およびCSV形式のリストとして返します。

因数分解ツリーを作成するオプションと、指定された数のすべての因子を見つける可能性もあります。これらのオプションは両方とも、対応するボックスにチェックマークを付けることで選択できます。

入力値の制限

• 入力値は整数である必要があります。小数と分数は使用できません。
• 1 より大きい正の整数のみを入力として使用できます。
• 数値の長さは13桁 (千を区切るためのコンマなし) を超えることはできません、つまり、入力数値の値は10, 000,000,000,000または1000000000000000未満である必要があります。したがって、最大入力値は 9,999,999,999,999 または 9999999999999 です。

素数と合成数

素数とは、1 より大きい整数であり、これ以上他の整数に分割することはできません。つまり、素数とは、他の整数を掛け合わせても作れない 1 より大きい整数のことです。最小の素数は2, 3, 5, 7, 11, 13, 17, … (1つの素数だけが偶数であることに注意してください– 2、他のすべての素数は奇数です).

上記のリストの n 番目の素数は、Prime[n] と表すことができます。その場合, Prime [1] = 2, Prime [2] = 3, Prime [3] = 5, 等々。 このオンライン計算機は、n = 5000 までの識別された各素数のインデックス n を示します。

合成数は、他の整数を乗算することによって作成できる1より大きい整数です。たとえば、6 = 3 × 2 であるため、6 は合成数です。12 = 6 × 2 = 3 × 2 × 2 であるため、12 は合成数です。

数値因数分解

別の整数を得るために乗算する数値は、因数と呼ばれます。上記のように、3と2は6の因数です。6は1と6を掛けることによっても見つけることができるので: 6 = 1 × 6、1 と 6 も 6 の約数です。最後に、6 のすべての約数は 1、2、3、6 です。 素数の唯一の因数は1と数自体です。たとえば、係数 17 は 1 と 17 です。

素因数分解は、与えられた数を作るために乗算できるすべての素数を見つけるプロセスです。数の素因数分解は、その数のすべての因数を見つけることとは異なることに注意してください。

たとえば、12のすべての因数は1、2、3、4、6、12です。これらの要因はリストとして書かれています。

12の素因数分解は次のようになります: 12 = 2 × 2 × 3. 素因数分解では、素数の形でのみ結果が得られます。

素因数分解アルゴリズム

トライアル部門

最も直観的な素因数分解法 (試行除算法とも呼ばれます) を例として見て、36 の素因数を特定します。すべての素数を知っているので、与えられた数がそれらのいずれかで割り切れるかどうかを確認できます。 最も簡単な方法は、2 である最小の素数から始めることです:

36 ÷ 2 = 18

この除算の結果は整数です。したがって、2は36の素因数の1つです。しかし、18はまだ素数ではないので、続けて18が2で割り切れるかどうかを確認します:

18 ÷ 2 = 9

9も整数です。したがって、18は2で割り切れます。

もう一度やり直しましょう: 9 ÷ 2 = 4.5. これは整数ではありません。したがって、9は2で割り切れません。 次の素数3を試してみましょう。9 ÷ 3 = 3。これは整数なので、うまくいきました! さらに、3はすでに素数であり、プロセスの最終ステップに到達したことを意味します。今、私たちは最終的な答えを書き留める必要があります:

36 = 2 × 2 × 3 × 3

これは、数の素因数分解を書き留める一般的な方法です。このような指数を使用して記述することもできます:

36 = 2² × 3²

素因数ツリー

素因数分解プロセスは、”木”として説明することもできます。36の素因数木は次のようになります:

試験区分(任意の要因)

素因数分解プロセスは、最初に他の2つの (素数ではない) 数の乗算として数値を表現し、次にそれらの素因数を特定すると、より簡単になります。たとえば、48の素因数を見つけましょう。あなたはおそらくそれを心から知っているので、48 = 6×8から始める方が簡単です。次に、6の素因数を見つける必要があります: 6 = 2 × 3, and 8: 8 = 2 × 2 × 2. Finally, 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹.

算術の基本定理

1より大きい正の整数は、素因数の一意のセットから作成できます。この定理は、素因数分解定理と呼ばれることもあります。

実際のアプリケーション

素数は、暗号化とサイバーセキュリティでメッセージの暗号化と復号化に使用されます。任意の数が素数の集合の積として表すことができ、この集合が一意であることはすでにわかっています。素数のこの品質は、それらを暗号化に非常に便利にするものです。

さらに便利なのは、非常に大きな数の素因数を見つけることは、現代のコンピューターであっても、非常に時間のかかる作業のままであるということです。このページの計算機が無限に大きな数で機能しないのもそのためです。

暗号化に素数を使用する背後にある中心的な原則は、2つの大きな素数を取り、それらを乗算してはるかに大きな合成数を作成することが比較的簡単であるということです。ただし、その最終的な数を元の素数に分解することは非常に困難です。

2つの10桁の素数を取り、それらを乗算して、さらに多くの桁の数を取得することを想像してみてください。ここで、試行除算によるその数の素因数分解のプロセスを想像してみてください…

これは非常に長いプロセスであるため、現在、コンピューターは特定の問題で2つの初期素数を妥当な時間内に見つけることができません。しかし、この状況は、量子コンピューターの開発により将来変わる可能性があります。