素数

Kanapedia 数学カテゴリ

素数（prime number）は、1より大きい自然数のうち、正の約数が1とその数自身だけである数である。

例

2, 3, 5, 7, 11, 13, 17, 19, …

4は2×2と分解できるので素数ではない。1は現代的な定義では素数に含めない。

素数が有限個 p₁,…,pₙ しかないと仮定し、

N=p₁p₂…pₙ+1

を考える。Nは列挙したどの素数で割っても余り1となるため、N自身が素数か、一覧にない素因数を持つ。これは仮定に矛盾する。

素数は整数の「乗法的な部品」とみなせる。整数の素因数分解、素数の分布、暗号理論などで中心的役割を持つ。

2以上の整数は素数の積に分解でき、その表し方は順序を除いて一意である。例えば360=2³×3²×5となる。もし1を素数に含めると、任意の個数の1を積に付け加えられ、素因数分解の記述に不要な曖昧さが生じる。最大公約数と最小公倍数も素因数の指数を比較して求められる。

合成数n=abでa,b>1なら、両方が√nより大きいとab>nとなって矛盾する。したがって少なくとも一方は√n以下で、その約数の素因数も√n以下である。97なら√97<10なので2,3,5,7で割れないことを確認すれば素数と分かる。

エラトステネスのふるいは、ある上限までの素数をまとめて列挙する方法である。素数pの倍数を消す際、p²より小さい合成倍数はより小さい素数で既に消えている。巨大整数一つの素数判定と、合成数の素因数を探す問題は異なる。試し割りが遅いからといって、素数判定全体が同じ計算量だとは結論できない。

221は素数か。√221<15を使って調べよ。

解答と考え方を見る

221=13×17なので合成数。2,3,5,7,11だけで割れないことを確認して終えると、13という約数を見落とす。

資料確認日：2026-10-12。