やまでら くみこ のレシピ

短時間で簡単に作れる人気家庭料理を紹介。

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

投稿日:

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

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

整数

入力は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と自分自身以外に割り切れる数はない」ということです。

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

おすすめ記事

分数の計算機ツール。分数のかけ算・割り算・足し算・引き算を簡単に。

分数同士の計算をサイト上で簡単に行える、電卓アプリです。かけ算・割り算…

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

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

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

素因数分解をサイト上で簡単に行える、計算機アプリです。入力は15桁以下…

最小公倍数の計算アプリ。手計算する場合の簡単な求め方も紹介。

最小公倍数を求めるための計算機アプリです。整数は、3つ以上入力すること…

最大公約数の計算機。サイト上で瞬時に計算!簡単な求め方も解説。

最大公約数を求めるための計算機アプリです。整数は、3つ以上入力すること…

フランス語のアルファベットの簡単キーボード。一覧から文字を入力。

フランス語のアルファベットを簡単に入力するためのオンラインアプリです。…

スペイン語のアルファベット入力キーボード。変換不要!一覧から文字を選択

スペイン語のアルファベットを簡単に入力するためのオンラインアプリです。…

ロシア語のアルファベット入力キーボード。変換不要!一覧から文字を選択

ロシア語のアルファベットを簡単に入力するためのオンラインアプリです。一…

累乗・べき乗の計算機。指数が分数・小数・マイナスでもOK!

累乗とべき乗(冪乗)を簡単に計算する電卓です。数aのn乗、anを算出し…

正三角形の面積・高さ・辺の長さの計算機。公式を使った求め方も紹介。

正三角形の面積・高さ・辺の長さを計算するツールです。

円の面積・直径・半径・円周の計算機。公式を使った求め方も紹介。

円の面積と円周の長さを計算するツールです。

トルコ語のアルファベットの入力ツール。トルコ文字の簡単キーボード。

トルコ語のアルファベットを入力するためのオンラインツールです。使い方は…

ギリシャ文字への変換を簡単に!見た目と読み方の一覧からギリシャ語を入力。

ギリシャ文字を手軽に入力するためのオンラインツールです。入力したいギリ…

ページ内リンクのジャンプ先がずれる原因と解決方法【HTML】

ページ内リンクのジャンプ先がずれてしまう原因と、その解決策について解説…

平方根(ルート)の値を求める計算機。分数もOKな電卓サイト。

平方根(ルート)の計算機は、平方根の値をサイト上でカンタンに計算できる…