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

公開ツール素数判定・素数一覧生成ツール

目次
  1. 素数かどうかの判定でつまずく場面
  2. 素数を手で判定する計算の順序
  3. 判定結果を読むときに混同しやすい点
  4. まとめ
  5. よくある質問

ある数が素数かどうかを判定するには、決まった計算の順序があります。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万までに制限されます。

この記事は韓国語の原文をもとに作成しています。 韓国語の原文を読む

関連記事

  1. 手形割引計算の仕組み|割引料と手取り額の求め方手形の割引料は額面×年割引率×(残り日数/基準日数)で求めます。例の数字で計算を追い、365日・360日の違いや割引開始日の選び方で手取り額がどう変わるかを整理しました。
  2. 比例式の解き方|外項・内項の積と未知数の位置A:B = C:D で外項の積と内項の積が等しい性質を、未知数の位置ごとに実際の代入で解説します。手計算の手順と比例式計算機の使い方もわかります。
  3. 坪と平方メートルの変換方法|32坪と84㎡の違いも解説1坪=3.3058㎡の根拠と換算式を確認し、専有面積84㎡が「32坪」と呼ばれる理由や、専有面積と供給(分譲)面積の違いを計算例で整理します。
  4. 三平方の定理の計算方法|斜辺を求める3ステップ三平方の定理(a²+b²=c²)で斜辺や残りの辺を求める手順を、2乗・和・平方根の3ステップで解説します。辺の選び間違いや成り立たない例も確認できます。
  5. 二次方程式の解の公式と判別式Dの使い方判別式D=b²-4acの符号で実数解・重解・虚数解を見分け、解の公式に係数を代入して答えを求めるまでの計算手順を、例題つきで順を追って解説します。
  6. 賃貸利回りの計算方法|キャップレートと自己資金利回り賃貸の利回りはキャップレートと自己資金利回り(CoC)の2種類。NOI・利息・自己資金の出どころを、計算ツールに含まれない取得税や仲介手数料まで含めて整理します。

関連ツール