素数の判定方法:平方根までで足りる理由

ある数が素数かどうかを判定するには、決まった計算の順序があります。1は定義上、最初から対象外です。次に2と3を確認し、残った候補は平方根まで割ってみれば結論が出ます。
素数判定のロジックを理解したい方や、特定の数を手で検算してみたい方がつまずく箇所は、たいていこの順序の中にあります。
要約 ① 素数は「1と自分自身だけを約数に持つ、1より大きい自然数」なので、1は定義上除外されます。 ② 2と3を先に取り除くと、残る候補は6で割った余りが1または5の数に絞られます。 ③ n=a×bのとき、aとbのどちらか一方は必ず平方根以下になるため、平方根まで割ってみれば十分です。
素数かどうかの判定でつまずく場面
2桁や3桁の数を手で確認していると、どこまで割れば止めてよいのか分からなくなることがあります。
たとえば91が素数かどうかを調べるとき、2でも3でも割り切れないので、そのまま5、7、11、13……と割っていく必要がありそうに思えます。ところが、止めどきの基準がないと、いつまでも割り続けることになってしまいます。
プログラミングの問題を解くときも、同じところでつまずきます。「nが素数かどうかを判定する関数を書きなさい」という問題では、「平方根まで割れば十分」というヒントがよく出てきます。しかし、なぜそれでよいのか根拠が分からなければ、コードを丸暗記して書くのと変わりません。
答えだけを知っていて計算の原理を理解していないと、数が少し大きくなっただけで(5桁、6桁など)、検算が合っているかどうかさえ自分では確認できなくなります。判定の順序を一度きちんと整理しておけば、この問題は解決します。
素数を手で判定する計算の順序
以下の順序は、判定ツールが内部で行っている計算の順序と同じです。この順序どおりに進めれば、どんな自然数でも手で素数かどうかを確認できます。
ステップ1〜2: 1を除外し、2と3から確認する
素数の定義は「1より大きい自然数のうち、1と自分自身だけを約数に持つ数」です。1は約数が自分自身(1)だけなので、この定義に当てはまらず、最初から対象外になります。2と3はそれぞれ最小クラスの素数なので、そのまま素数と判定されます。
ステップ3〜4: 2と3の倍数を取り除いて候補を絞る
残った数が2の倍数(偶数)または3の倍数であれば、その時点で素数ではないと分かり、割り切れた値(2または3)が約数として表示されます。たとえば51は3で割り切れるので、この段階ですぐに合成数と判定されます。
2と3の倍数をすべて除くと、残るのは6で割った余りが1または5の数だけです(6k+1、6k+5の形)。
そのため、5から始めて5、7、11、13、17、19のように6ずつ進みながら、2つの候補(i、i+2)だけを割ってみれば、それ以外のケースは調べる必要がありません。
ステップ5: 平方根まで割ってみて、そこで止める
n = a × bと割り切れるなら、aとbのうち少なくとも一方は必ず√n以下です。両方が√nより大きいと、積がnを超えてしまうからです。したがって、√nまでに割り切れる値がなければ、その数は素数と確定します。
91と97で実際に確かめる
91は2の倍数でも3の倍数でもないので、ステップ3を通過します。√91は約9.54なので、割ってみる候補は5と7だけです。
91を5で割ると割り切れませんが、7で割ると91 = 7 × 13と割り切れます。このため、91は合成数で、約数は7という結論になります。
では97はどうでしょうか。同じく2や3の倍数ではなく、√97は約9.85なので、候補はやはり5と7です。どちらも97を割り切れないため、それ以上確認する必要はなく、97は素数と確定します。
手でこの順序をたどったあとに、同じ計算をツールがどのように即座に処理するかを見比べると、理解が早まります。「素数判定・素数一覧生成ツール」で確認してみましょう。
数を入力すると素数かどうかと約数をすぐに表示し、範囲を指定すれば素数の一覧もその場で生成できる無料ツールです。

判定結果を読むときに混同しやすい点
素数の判定結果そのものは明確ですが、画面に表示される文言を解釈するときに、誤解しやすい点が2つあります。
「約数」として表示される値は、その数のすべての約数ではなく、判定の過程で最初に割り切れた値、つまり最小の素因数です。91の実際の約数は1、7、13、91の4つですが、画面には計算中に最初に見つかった7だけが表示されます。
数が大きくなるほど、√nまで割ってみる候補の数も増えます。100万に近い7桁の数では√nが1000付近になり、6間隔の最適化を使っても、数百個の候補を割らないと判定が終わりません。このあたりからは、手での検算は現実的ではありません。
| 画面に表示される表現 | 実際の意味 |
|---|---|
| 「素数ではありません、約数: 7」(91の場合) | 91のすべての約数(1、7、13、91)ではなく、最小の素因数である7を示しています |
| 「素数」 | 1と自分自身以外に、√nまでで割り切れる値がなかったことを示しています |
| 入力欄が空、または数字以外のとき | NaNとして扱われ、エラーとして表示されます |
まとめ
- 素数は、1より大きい自然数のうち、1と自分自身だけを約数に持つ数です。約数が1つしかない1は、定義上除外されます。
- 2と3を先に確認してその倍数を取り除くと、残る候補は6で割った余りが1または5の数に絞られます。
- n = a × bのとき、a、bのどちらか一方は必ず√n以下なので、√nまで割れば素数かどうかを確定できます。
- 画面に表示される「約数」は、その数のすべての約数ではなく、計算中に最初に見つかった最小の素因数です。
- 桁数が大きくなるほど割ってみる候補の数も増えるため、手で検算するより判定ツールですぐに確認するほうが正確です。
数を入力すると素数かどうかと約数をすぐに表示し、範囲を指定すれば素数の一覧もその場で生成できる無料ツールです。
よくある質問
1はなぜ素数ではないのですか?
素数の定義は、1より大きい自然数のうち、1と自分自身だけを約数に持つ数です。1は約数が自分自身(1)だけなので、この条件に当てはまりません。そのため、1は素数でも合成数でもない、別の数として扱われます。
判定結果に出る「約数」は、その数のすべての約数ですか?
いいえ。計算の過程で最初に割り切れた値が1つだけ表示されます。これは常に、その数の最小の素因数です。91は実際には1、7、13、91の4つの約数を持ちますが、画面には7だけが表示されます。
偶数の中で素数が2だけなのはなぜですか?
2より大きい偶数はすべて2で割り切れるため、約数が1、2、自分自身の3つ以上になり、素数の条件を満たせません。2は偶数でありながら、約数が1と2の2つだけという唯一のケースなので、素数として残ります。
素数の一覧はどのような方法で作られますか?
エラトステネスのふるいを使っています。2から指定した範囲までの数を並べておき、素数の倍数を順番に消していって、最後まで残った数だけを素数とする方法です。
入力できる範囲は最大100万で、これを超える値を入力すると、自動的に100万までに制限されます。
この記事は韓国語の原文をもとに作成しています。 韓国語の原文を読む