素数判定プログラム。素数を見分けるためのフローチャートも紹介。

この素数チェッカーは、指定した整数が素数かどうかを簡単に判定できるアプリです。

もし素数でない場合は、その整数の素因数を一覧表示します。
また、その整数に値が近い素数も参考として表示します。

整数

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

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

素数の意味

素数とは、1と自分自身以外に約数を持たない正の整数のことです。
英語では、prime numberといいます。

たとえば、2や3や5は素数ですが、4や6や9は他の数でも割りきれるので素数ではありません。
また、1の約数は1だけなので、こちらも素数の定義からは外れます。

ちなみに、素数は無限に存在します。
そのため、素数の最大値というのはありません。

素数の見分け方・見つけ方

整数nが素数かどうかを調べるには、次のようなアルゴリズムで計算します。

2で割る

整数nをまず2で割ってみます。
これで割り切れれば素数ではありません。

奇数で順に割っていく

2で割り切れない場合は、3以上の奇数で順に割っていきます。
具体的には、3・5・7・9と同様の処理を繰り返します。

整数nの平方根を超えるまで処理を繰り返す

奇数で割る処理は、その対象の奇数が、整数nの「正の平方根の値」を超えるまで繰り返します。
たとえば、整数nが53の場合は、53の正の平方根は約7.2なので、7.2以下の最大の奇数である7で割った時点で処理終了です。
2から始まって、7に至るまでずっと割り切れなかったということで、53が素数であることが確定します。

では、なぜ「正の平方根の値」を超えたら処理を終えるのか。
それは、整数nを2つの整数の積で表現する場合、その2つの整数のどちらか一方は、かならず整数nの正の平方根以下の数になるためです。

たとえば、36という数字は2×18や3×12と表現することができますが、2も3も、36の正の平方根である6以下の数となっています。
これは、言い換えると、「正の平方根以下の数字で片っ端から割ってみて割り切れなければ、1と自分自身以外に割り切れる数はない」ということです。

そのため、この理屈を素数判定に応用できるというわけです。