素数とは?
素数とは、1より大きい整数のうち、正の約数が「1」と「その数自身」の2つだけであるものを指します。たとえば 2、3、5、7、11、13 などが素数です。1より大きい数で素数ではないものは「合成数」と呼ばれ、より小さい整数同士の積として表すことができます。この計算機を使えば、入力した数が素数かどうかを瞬時に判定でき、素数でない場合はその数を割り切る最小の約数も表示します。
計算機の使い方
入力欄に0以上の整数を入力して送信するだけです。結果表示エリアには、素数であればはい、合成数であればいいえと表示されます。合成数の場合は、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とその数自身のみであるものです。自然数\(n\)を調べるには、\(\lfloor\sqrt{n}\rfloor\)以下の約数を探すだけで十分です。\(n\)が平方根より大きい約数を持つなら、平方根より小さい対応する約数も必ず持っています。
- \(n < 2\)を除外する。 0、1および負の数は素数ではありません。
- 2と3を素数と認める。 どちらも素数です。2は唯一の偶数の素数です。
- 偶数を除外する。 2より大きい偶数\(n\)は2で割り切れるので、合成数です。
- \(\lfloor\sqrt{n}\rfloor\)を計算する。 二乗が\(n\)以下となる最大の整数を求めます。例えば、\(14^2 = 196 \le 221 < 225 = 15^2\)なので、\(\lfloor\sqrt{221}\rfloor = 14\)です。
- 3から\(\lfloor\sqrt{n}\rfloor\)までの奇数の約数、または素数だけを調べる。 各候補\(d\)について\(n \bmod d = 0\)かどうかを確認します。以下の割り算の簡単な判定法を使うと速くなります。
- 判定する。 約数が見つかれば、\(n\)は合成数であり、最初に見つかった約数が1より大きい最小の約数です。どれも\(n\)を割り切らなければ、\(n\)は素数です。
割り算の簡単な判定法
- 3で割り切れるか:各桁の和が3で割り切れる。例:51は5 + 1 = 6なので、51 = 3 × 17。
- 5で割り切れるか:一の位が0または5である。
- 11で割り切れるか:各桁の交互の和を、右から、または左から取る。結果が0または11の倍数であれば、その数は11で割り切れる。例:121は1 − 2 + 1 = 0なので、121 = 11 × 11。
計算例1:221は素数か?
- 221 ≥ 2であり、奇数で、2でも3でもない。
- \(\lfloor\sqrt{221}\rfloor = 14\)なので、素数の3、5、7、11、13を調べる。
- 3:各桁の和は2 + 2 + 1 = 5で、3で割り切れないので、割れない。
- 5:一の位は1なので、割れない。
- 7:\(7 \times 31 = 217\)で、\(221 - 217 = 4\)なので、余りが出て割れない。
- 11:交互の和は1 − 2 + 2 = 1なので、割れない。
- 13:\(13 \times 17 = 221\)なので、13は221を割り切る。
221は合成数で、その最小の約数は13です。
計算例2:97は素数か?
- 97は奇数で、3より大きい。
- \(9^2 = 81 \le 97 < 100 = 10^2\)なので、\(\lfloor\sqrt{97}\rfloor = 9\)。3、5、7を調べる。
- 3:各桁の和は9 + 7 = 16で、3で割り切れないので、割れない。
- 5:一の位は7なので、割れない。
- 7:\(7 \times 13 = 91\)で、\(97 - 91 = 6\)なので、余りが出て割れない。
9以下のどの約数も97を割り切らないので、97は素数です。
この手計算の方法は小さな数や中くらいの数に適しています。非常に大きな数では、試し割りは遅くなるため、代わりに専用の素数判定法が使われます。
計算の約束事と境界ケース
以下の各ケースは実際にこの計算ツールで計算したもので、結果欄はツールが返す値そのものです。
| ケース | 入力 | 結果 |
|---|---|---|
| 1 は素数か | 1 | いいえ |
| 2 は素数か | 2 | はい |
| 0 は素数か | 0 | いいえ |
2026-11-08に確認
よくある質問
1は素数ですか? いいえ。定義上、素数は1より大きい数でなければならないため、1は素数でも合成数でもありません。
2は素数ですか? はい。2は唯一の偶数の素数です。これ以外の偶数はすべて2で割り切れます。
なぜ平方根までしか調べないのですか? 約数は、掛け合わせるとnになるペアで存在します。もしそのペアの両方が \(\sqrt{n}\) より大きければ、積はnを超えてしまい矛盾します。したがって、どのペアにも必ず \(\sqrt{n}\) 以下の約数が含まれるのです。