素数とは?
素数とは、1より大きい整数のうち、正の約数が「1」と「その数自身」の2つだけであるものを指します。一方、約数が3つ以上ある数は合成数と呼ばれます。なお「1」は特別で、約数が1つ(自分自身)しかないため、素数でも合成数でもありません。このツールでは、入力した数が素数か合成数かを判定し、約数の一覧、さらに直前の素数と直後の素数を表示します。
$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$
使い方
1より大きい整数を入力欄に入れて送信するだけです。ツールはその数を素数か合成数かに分類し、入力値を再表示したうえで、合成数の場合はすべての約数を一覧表示します。あわせて、その数より小さい最大の素数と、より大きい最小の素数も示します。
計算のしくみ
このツールでは「6k±1の最適化」を用いた確定的な試し割り法(trial division)を採用しています。まず2と3を素数として扱い、偶数や3の倍数を除外します。次に、6k−1・6k+1の形をした候補(5, 7, 11, 13, …)だけを、n の平方根まで割り算して調べます。どれでも割り切れなければ n は素数です。平方根までで十分な理由は、平方根より大きい約数は必ず平方根より小さい約数とペアになるためです。
具体例で確認
\(n = 97\) で考えてみましょう。平方根は約9.85です。97は奇数で、3の倍数でもありません。そこで5(\(97 \div 5\)の余りは2)と7(\(97 \div 7\)の余りは6)を試します。次の候補は11ですが、$$11 \times 11 = 121 > 97$$なので、ここで打ち切ります。割り切れる数は見つからなかったので、97は素数です。直前の素数は89、直後の素数は101になります。
素数と合成数:入力例の比較
この表は、試し割り法が7つの入力をどのように扱うかを示しています。平方根の上限は\(\lfloor\sqrt{n}\rfloor\)であり、試す必要がある最大の約数です。この上限以下の2からのどの整数も\(n\)を割り切らない場合、\(n\)は素数です。直前の素数と直後の素数は、\(n\)より厳密に小さい、または大きい最も近い素数です。
| 入力 n | 判定 | すべての約数 | 直前の素数 | 直後の素数 | 平方根の上限 \(\lfloor\sqrt{n}\rfloor\) |
|---|---|---|---|---|---|
| 2 | 素数 | 1, 2 | なし | 3 | 1(試す約数なし。2は唯一の偶数の素数です) |
| 9 | 合成数 | 1, 3, 9 | 7 | 11 | 3(3が9を割り切る) |
| 15 | 合成数 | 1, 3, 5, 15 | 13 | 17 | 3(3が15を割り切る) |
| 49 | 合成数 | 1, 7, 49 | 47 | 53 | 7(7が49を割り切る) |
| 91 | 合成数 | 1, 7, 13, 91 | 89 | 97 | 9(7が91を割り切る) |
| 97 | 素数 | 1, 97 | 89 | 101 | 9(2, 3, 5, 7, 9はいずれも97を割り切らない) |
| 121 | 合成数 | 1, 11, 121 | 113 | 127 | 11(11が121を割り切る) |
素数に見える合成数: 49、91、121は奇数で、3や5で割り切れないため、素数と間違えやすい数です。
- \(49 = 7 \times 7\)
- \(91 = 7 \times 13\)
- \(121 = 11 \times 11\)
いずれも平方根の上限以下に約数があるため、2、3、5だけを調べると誤って素数と判定してしまいます。対照的に、97は9までに約数がないので、素数です。
主要な用語と定義
- 素数
- 1より大きい整数で、正の約数が1と自分自身だけのもの(例:2、3、5、7、97)。
- 合成数
- 1より大きい整数で、1と自分自身以外の約数を少なくとも1つ持つもの(例:9、49、91)。0と1は素数でも合成数でもありません。
- 因数 / 約数
- \(n\)を余りなく割り切る整数\(d\)。15の場合、因数は1、3、5、15です。
- 剰余(mod)
- 割り算の余り。\(n \bmod d = 0\)は、\(d\)が\(n\)をちょうど割り切ることを意味します。例えば、\(91 \bmod 7 = 0\)ですが、\(97 \bmod 7 = 6\)です。
- 平方根の上限
- \(n = a \times b\)かつ\(a \le b\)ならば、\(a \le \sqrt{n}\)です。したがって、どの合成数も2から\(\lfloor\sqrt{n}\rfloor\)の間に約数を持ち、それ以上調べる必要はありません。
- 試し割り法
- \(n\)を2から\(\lfloor\sqrt{n}\rfloor\)までの候補の約数で割る素数判定法。いずれかの割り算で余りが0になれば\(n\)は合成数で、そうでなければ素数です。単純で信頼性が高く、中程度の大きさの数に対しては高速です。
- 6k±1形式
- 3より大きいすべての素数は、ある整数\(k\)について\(6k-1\)または\(6k+1\)と書けます。6を法とする他の剰余は2または3で割り切れるためです。これにより、判定では候補の約数のおよそ3分の2を飛ばすことができます。逆は成り立ちません。25、35、49、91はこの形式ですが合成数です。
- 双子素数
- 差が2である2つの素数の組。例えば(3, 5)、(11, 13)、(17, 19)、(41, 43)など。双子素数の組が無限に存在するかどうかは、数学における未解決問題です。
計算の約束事と境界ケース
以下の各ケースは実際にこの計算ツールで計算したもので、結果欄はツールが返す値そのものです。
| ケース | 入力 | 結果 |
|---|---|---|
| 1 は素数か | 1 | 素数でも合成数でもない |
| 2 は素数か | 2 | 素数 |
| 0 は素数か | 0 | 無効 |
2026-11-08に確認
よくある質問
1は素数ですか? いいえ。1は約数が1つしかないため、素数でも合成数でもありません。
2は素数ですか? はい。2は最小の素数であり、唯一の偶数の素数です。これより小さい素数は存在しません。
なぜ約数の一覧は合成数のときだけ表示されるのですか? 素数は定義上「1とその数自身」しか約数を持たないため、その旨を示すだけで十分です。合成数は多くの約数を持つことがあるので、小さい順に一覧表示します。