素数チェッカー

最終更新: 2026-05-18

素数とは何か

素数とは、1より大きい自然数のうち、1と自分自身以外に正の約数をもたない数のことです。言い換えれば、2つの自然数の積として表せない（自明な積を除く）数です。

• 2 は素数：1と2でしか割り切れない
• 7 は素数：1と7でしか割り切れない
• 12 は素数ではない（合成数）：1、2、3、4、6、12で割り切れる

最初の20個の素数は次のとおりです。

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71$

素数は数が大きくなると出現頻度が下がりますが、無限に存在します。ユークリッドは紀元前300年頃、素数が無限に存在することを背理法で証明しました。

1が素数ではない理由

現代の定義では、素数は正の約数をちょうど2個もつ数です。1の正の約数は1だけで2個に満たないため、この条件を満たしません。1と自分自身のほかに約数をもたない点は素数と共通しますが、約数の個数の条件で区別されます。

より本質的な理由は算術の基本定理（素因数分解の一意性）を守るためです。仮に1を素数とすると、

$12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 = \cdots$

のように、同じ数の素因数分解が無限通りできてしまいます。1は「単元」と呼ばれ、素数でも合成数でもない特別な数として扱われます。

試し割り法

素数判定の基本的な手法が試し割り法です。数 $n$ が素数かどうかを確認するには、$\sqrt{n}$ 以下の素数で割り切れるかどうかを調べれば十分です。$\sqrt{n}$ を超える約数があれば、その相方として $\sqrt{n}$ 以下の約数が必ず存在するためです。

$\sqrt{1000} \approx 31.6$ なので、31以下の素数（2、3、5、7、11、13、17、19、23、29、31）で割り切れるかどうかを確認すれば、1〜1000の範囲のすべての整数を素数判定できます。

例：97は素数か？

除数	$97 \div d$	余り
2	48.5	1
3	32.3…	1
5	19.4	2
7	13.857…	6

$\sqrt{97} \approx 9.8$ 以下の素数で割り切れないので、97は素数です。

例：91は素数か？

$91 \div 7 = 13$（余り0）なので、7で割り切れます。よって 91は合成数（$91 = 7 \times 13$）で、最小素因数は7です。

エラトステネスの篩

ある上限まですべての素数を列挙したいときは、エラトステネスの篩が効率的です。

1. 2から $N$ までの整数を並べる
2. 2の倍数（4、6、8…）を消す
3. 次の消されていない数（3）の倍数（6、9、12…）を消す
4. $\sqrt{N}$ に達するまで繰り返す

残った消されていない数がすべて素数です。時間計算量は $O(N \log \log N)$ で、個別に試し割りするよりはるかに高速です。

暗号と素数の関係

現代の通信暗号は、素数がもつ計算の非対称性を利用しています。2つの大きな素数を掛け合わせる計算は容易ですが、その積を素因数分解して元の素数を求める計算は、桁数が大きくなるほど急激に困難になります。

RSA暗号（HTTPSやデジタル署名で使われる公開鍵暗号）の仕組みは次のとおりです。

1. 巨大な素数 $p$ と $q$ を選ぶ（通常1024〜4096ビット）
2. $n = p \times q$ を計算し、公開鍵の一部として公開する
3. 鍵を解読するには $n$ を $p$ と $q$ に因数分解する必要があるが、現在の計算機では現実的な時間内に完了しない

この「掛け算は容易だが因数分解は困難」という一方向性が、公開鍵暗号の安全性の根拠になっています。

判定例の一覧

数	素数？	最小素因数
1	いいえ（単元）	—
2	はい	2（自身）
4	いいえ	2
17	はい	17（自身）
49	いいえ	7
97	はい	97（自身）
100	いいえ	2
997	はい	997（自身）

よくある質問 (FAQ)

素数とは何ですか？

素数とは、1より大きい自然数のうち、1と自分自身以外に正の約数をもたない数です。例えば、2・3・5・7・11・13はすべて素数です。12は1・2・3・4・6・12で割り切れるので素数ではありません。1より大きいすべての整数は素数か、素数の積として一意に表せます（算術の基本定理）。

なぜ1は素数ではないのですか？

素数の定義では「正の約数がちょうど2個（1と自身）」という条件が必要です。1の正の約数は1のみで2個になりません。歴史的には1を素数とする流儀もありましたが、算術の基本定理（素因数分解の一意性）を成立させるために、現代数学では1を素数から除外しています。仮に1が素数なら素因数分解が無数に生じてしまいます。

最初の10個の素数は何ですか？

最初の10個の素数は 2、3、5、7、11、13、17、19、23、29 です。2は唯一の偶数の素数で、それ以外の偶数は必ず2で割り切れるため合成数です。素数は数が大きくなるにつれて出現頻度が下がりますが、無限に存在することはユークリッドが証明しています。

素数が暗号に重要な理由は何ですか？

RSA暗号をはじめとする公開鍵暗号は、「大きな2つの素数の積を計算するのは簡単だが、積から元の素数を因数分解するのは計算コストが非常に高い」という非対称性を利用しています。現在のRSA鍵は数百桁の素数を使用しており、この困難さがHTTPSやデジタル署名の安全性を支えています。