素数とは？
素数とは、1より大きい整数のうち、正の約数が「1」と「その数自身」の2つだけであるものを指します。たとえば 2、3、5、7、11、13 などが素数です。1より大きい数で素数ではないものは「合成数」と呼ばれ、より小さい整数同士の積として表すことができます。この計算機を使えば、入力した数が素数かどうかを瞬時に判定でき、素数でない場合はその数を割り切る最小の約数も表示します。
計算機の使い方
入力欄に0以上の整数を入力して送信するだけです。結果表示エリアには、素数であればYES、合成数であればNOと表示されます。合成数の場合は、1より大きい最小の約数が表に示されるので、そこから素因数分解を進める手がかりになります。
計算の仕組み
素数判定を効率よく行うには、nの平方根までの約数だけを調べれば十分です。もしnが平方根より大きい約数を持つなら、それに対応する平方根より小さい約数も必ず存在するため、平方根までを確認すれば事足ります。式で表すと、n が素数であるのは次が成り立つときです。
$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$つまり「\(n > 1\) かつ、2 から \(\lfloor\sqrt{n}\rfloor\) までのすべての整数 \(i\) について \(n \bmod i \neq 0\)」が成り立つときです。これにより、n未満のすべての数を調べる場合に比べて計算量を大幅に削減できます。
計算例
\(n = 97\) を考えてみましょう。平方根はおよそ 9.85 なので、約数として 2、3、5、7、9 を調べます。いずれも 97 を割り切ることはできず（97は奇数で、3でも5でも7でも割り切れません）、したがって 97 は素数です。次に \(n = 91\) を見てみましょう。2、3、5、そして 7 を試すと、$$91 \div 7 = 13$$とちょうど割り切れるため、91 は最小の約数を 7 とする合成数だとわかります。
よくある質問
1は素数ですか？ いいえ。定義上、素数は1より大きい数でなければならないため、1は素数でも合成数でもありません。
2は素数ですか？ はい。2は唯一の偶数の素数です。これ以外の偶数はすべて2で割り切れます。
なぜ平方根までしか調べないのですか？ 約数は、掛け合わせるとnになるペアで存在します。もしそのペアの両方が \(\sqrt{n}\) より大きければ、積はnを超えてしまい矛盾します。したがって、どのペアにも必ず \(\sqrt{n}\) 以下の約数が含まれるのです。
