素因数分解の簡単計算アプリ!ツールなしで算出するやり方も解説。

投稿日:

素因数分解をサイト上で簡単に行える、計算機アプリです。

整数

入力は15桁以下に抑えるのがおすすめです。
入力した数字が大きいと、計算にかなりの時間を要する場合があります。

なお、このツールは、計算にjavascriptライブラリmath.jsを使用しています。

素因数分解とは

素因数分解とは、正の整数を素数の積に分解することです。
例えば、20を素因数分解すると、22×5になります。

ちなみに、素数とは、1と自分自身しか約数を持たない数のこと。
2や3や5は素数ですが、4や6や9は他の数でも割りきれるので素数ではありません。

素因数分解のやり方

手計算で素因数分解する場合、次のようなアルゴリズムで計算します。

整数nの平方根(ルート)を求める

整数nを2つの整数の積で表現する場合、その2つの整数のどちらか一方は、かならず整数nの正の平方根以下の数になります。
たとえば、36という数字は2×18や3×12と表現することができますが、2も3も、36の正の平方根である6以下の数となっています。

こうした性質に着目して、まず最初に、整数nの正の平方根を求めます。
この数字をRとします。

整数nが36であれば、Rは6となります。

各素数で割り切れるか調べる

続いて、素数2を、整数nの素因数の候補としてひとまず設定します。

そして、実際に、素数2が整数nの素因数であるか検証します。
具体的には、整数nを2で割ってみて、割り切れれば素因数となります。

割り切れたら整数nの値を置き換える

割り切れた場合は、整数nを2で割った値を、新たに整数nに設定します。
たとえば、整数nが36の場合は、2で割った18が、新しい整数nの値になります。

そして、もう一度2で割ってみて、割り切れなくなるまで同様の処理を繰り返します。

整数nの平方根(ルート)を求め直す

割り切れなくなったら、素数2に関する処理は終了で、その時点の整数nをもとに正の平方根Rの値を新たに設定します。
たとえば、整数nが9の場合は、新しいRの値は3になります。

素数の値が整数nの平方根を超えたら終了

そして、素数2の次に大きい素数に移ります。
この処理を素数2・素数3・素数5と繰り返していき、対象の素数が、Rの値を超えた時点で計算は終了です。


素数かどうかの判別方法

以上が素因数分解のやり方になりますが、この方法を実践するためには、素数2から始まって、その次に大きい素数をスムーズに見つけていく必要があります。

2・3・5・7が素数であることは簡単に分かりますが、数字が大きくなるにつれて分かりづらくなってくるため、素数かどうかの判定方法も知っておくと便利です。

素数判定のコツ

素数の判定方法は、先ほどの素因数分解のやり方と似ています。
整数n’が素数かどうか調べるためには、まず整数n’の正の平方根R’を求めます。
R’が整数であれば、n’は素数ではありません。

R’が整数ではない場合は、整数n’を2で割ってみて、割り切れるかどうか調べます。
もし、割り切れたら整数n’は素数ではないということになります。

割り切れなかった場合は、1をプラスして3で割ってみる。
1づつ加算していき、R’以下の数字で割り切れなかったら、素数ということになります。