素数判定

素数 ⇔ d(n) = 2、n = 97のとき、d(n) = 2、previousPrime(97) = 97、nextPrime(97) = 97、nextPrime(1,000,000) = 1,000,003

n

判定される整数で、2から1,000,000までです。下限は引き継ぎではなく意図したものです。1の1つ前の素数は存在しないので、1を受け付けるページは正直に埋められない行を抱えることになります。1が素数かどうかは定義の問いで、計算機ではなく下のよくある質問で答えます

d(n)

正の約数の個数で、結果の1行目であり、判定が依拠する唯一の根拠です。d(n) = 2はそれを割り切る数がちょうど2つという意味で、これが素数の定義です。この個数は数論モジュール共通の手続きから来るので、同じ入力に対して約数のページや素因数分解のページが報告するのと同じ値になります

d(n) = 2

判定そのものを等式として述べたものです。近似ではなく同値です。ある数が素数であるのは、約数をちょうど2つ持つときで、そのときに限ります。97なら約数は1と97なので個数は2で、バッジは素数と読みます。100なら1、2、4、5、10、20、25、50、100なので個数は9で、バッジは合成数と読みます

previousPrime(n)

n以下でいちばん大きい素数です。上側が閉じているので、nが素数なら答えはn自身になります。100なら97、25なら23、97なら97です。区間を閉じているのは、そうしなければnがすでに素数のときに何を印字するかの規則が要り、結果欄の空行は事実ではなく失敗として読まれるからです

nextPrime(n)

n以上でいちばん小さい素数で、下側も同じく閉じています。25なら29、100なら101、97なら97です。こちらは入力の範囲を出ることがあります。nextPrime(1,000,000)は1,000,003で、このページが受け付けるどの数よりも大きい素数です。それでも範囲外として扱わず、答えとして報告します

1e6 to 1e6 + 100

入力の上限の近所と、そこだけ別の判定が要る理由です。100万の近くの素数は999,983と1,000,003なので、1,000,000から始める探索は片方向へ100万を越えて見に行かねばなりません。約数を数える手続きは100万を超える引数を拒否して例外を投げるので、隣の探索はその制限を持たない自前の判定を使います。両者は重なる範囲では一致していなければならず、例の中の素数の行がそれを確かめています

法を選ぶことが、自分で決めた数の近くに素数が欲しくなる最も実用的な理由です。ハッシュ表の枠の数はふつう素数にします。素数の法は公約数を持つ鍵を散らしてくれますが、そうでないと衝突させてしまうからです。枠が1,000の表は25の倍数をみな同じ少数の枠に送り込みますが、997の表はそうなりません。同じ発想が暗号にも当てはまり、そこでは大きく離れた素数から鍵を組み立てます。ある数が素数かどうかを調べると割り切れるかどうかの問いも素早く片づきます。平方根までの素数の約数を持たなければ、どの素数も持たないからです。バッジは試し割りを並べるのではなく一手でそれを答えます。双子素数や連続する素数の間隔、与えられた数が2つの素数の積かどうかといった、単に素数らしさについてのパズルもあります。問いが因数そのものについてだと分かったら、素因数分解のページがその数を素数に分けてくれ、自然な次の立ち寄り先になります。どの数が割り切るかという問いなら約数のページが全部並べます。調べている数が素数でなく、何からできているかを知りたいときは、このページの約数の個数が答えそのものではなく最初の手がかりになります。

1. 素数の場合：97

   1. 97の約数を試します。2では割り切れず、3でも5でも7でも11でも割り切れません
   2. 平方根で止めます。10 × 10 = 100がすでに97を越えているので、試すものはもう残っていません
   3. 約数は1と97だけなので個数は2で、この数は素数です
   4. 1つ前の素数は97自身です。97はすでに素数で、探索が閉じているからです
   5. 1つ後の素数も同じ理由で97です

   既定の入力であり、閉じた規則をいちばん素直に見せる例です。隣がどちらもその数自身で返るので、最初は行が何もしなかったように見えます。そうではありません。97以下でいちばん大きい素数は97であり、97以上でいちばん小さい素数も97です。厳密な不等号という代案では、このページが最も自信を持っている入力まさにそのもので2行が空になり、結果欄の空行はエラーとして読まれます。この場合はページ上の2つの独立した判定が出会う場所でもあります。約数の個数は2と言い、隣の探索も97は素数だと一致し、そこへ至るコードは別々です。

2. 合成数の場合：100

   1. 100は偶数なので2が割り切ります。末尾が00なので4、5、10、20、25、50も割り切ります
   2. 約数は1、2、4、5、10、20、25、50、100の9個です
   3. 9は2より大きいので、バッジは素数ではなく合成数と読みます
   4. 100以下でいちばん大きい素数は97、100以上でいちばん小さい素数は101です
   5. どちらの隣もその数のすぐ外側で、間隔の真ん中にいる合成数とはこういうものです

   隣が実際に仕事をしているのを見せる場合です。数が合成数のときは2行のほうが役に立つ出力になります。この数でなければどれか、という読者の次の問いに答えてくれるからです。97と101が最も近い素数で、100はその間にあります。約数の個数9も見る価値があります。奇数で、それが起きるのはその数が平方数のときちょうどで、100は10の2乗です。つまり個数を一目見るだけで、因数分解を始める前にその数の形について何かが分かります。

3. 素数のすぐ隣の数：25

   1. 25の約数は1、5、25の3個です。5が自分自身と組になるからです
   2. 3は2より大きいので、25は合成数です
   3. 25から下へたどります。24、23。23は素数なので、これが1つ前の素数です
   4. 25から上へたどります。26、27、28、29。29は素数なので、これが1つ後の素数です
   5. ここでの隔たりは合計6で、23と29が25を挟んでいます

   平方数なので約数の個数が奇数になり、しかも2つの隣までの距離が目に見えて違う例です。下が2、上が4です。個数が3であることは、しきい値が素因数の個数ではなく2であるべき理由も示しています。25の素因数は5の1つだけですが素数ではなく、約数の個数は因数分解をまったく見ずにそれを見抜きます。

入力は2から1,000,000までの整数でなければなりません。0と1は拒否し、1は0とは別の理由で拒否します。範囲外の数ではなく定義の問いであり、しかも1の1つ前の素数が存在しないからです。負の数も拒否します。素性は1より大きい整数の性質であり、数学の一部の分野には負の素数についての約束がありますが、このページはそれを採用していません。小数は丸めずに拒否します。上限の100万は入力にだけ掛かるもので、隣の2行は正当にその外側の素数を報告することがあります。100万の次に大きい素数は1,000,003で、それは拒否されずに報告されます。判定の裏にあるのは平方根までの試し割りで、この大きさなら一瞬、20桁の数なら絶望的です。その境界はこの実装ではなく問題そのものの性質です。このページが報告するのは3つの数とバッジだけです。約数そのものは並べず、合成数を因数分解もせず、範囲ではなく1つずつ判定します。下の参考表は入力に追随せず固定された行です。最後に、素数は自分自身を1つ前の素数かつ1つ後の素数として報告されます。これは閉区間という意図した選択であり、何も見つけられなかった2行ではありません。

1は素数ですか

いいえ、そして合成数でもありません。素数は1より大きい整数のうち正の約数をちょうど2つ持つものと定義され、1は約数を1つしか持たないのでどちらの条件でも外れます。これは見落としではなく意図した選択です。もし1を素数に数えると、すべての数が素因数分解をちょうど1つ持つという主張が成り立たなくなります。分解にいくらでも1を掛けられるからです。1を除くことがその定理をきれいに保っています。計算ではなく定義の問題なので、このページは1を入力として受け付けません。答えはここにあります

1つ前の素数も1つ後の素数もその数自身になるのはなぜですか

どちらの探索も閉じているからです。1つ前の素数はあなたの数より大きくない素数のうちいちばん大きいもので、1つ後の素数はあなたの数より小さくない素数のうちいちばん小さいものです。その数がすでに素数なら両方の記述を満たすので、2行ともその数を報告します。代わりに厳密な不等号にすると、素数の入力で2行とも印字するものがなくなります。結果欄の空行は何かがうまくいかなかったように読め、このページは最も自信のある場合に答えられなくなります。同じ約束は四捨五入にも現れます。すでに目標の精度にある数はそのまま返ります

入力が100万までなのに次の素数が100万を超えられるのはなぜですか

上限は尋ねられる値の制限であって、答えの値の制限ではないからです。1,000,000の次に大きい素数は1,000,003で、それを印字しないことは、このページが受け付けた入力についての完全に筋の通った問いに答えないことを意味します。そこで隣の探索は上限のない自前の判定で動き、約数の個数のほうは範囲だけを覆う共通の手続きを使い続けます。つまり素数かどうかを決める論理が2つあり、片方は範囲付きで片方はそうではありません。両者は重なる範囲で一致することが求められ、97の例がそれを確かめています。個数は2と言い、隣の探索も97は素数だと言います

素数は実際に何に使われるのですか

主に大きさを決めることです。ハッシュ表はふつう枠の数を素数にします。素数の法は公約数を持つ鍵を散らしてくれるからです。枠が1,000の表は25の倍数をみな同じ少数の位置に送り込みますが、997の表はそうなりません。同じ理屈は数が一周するあらゆる場所に当てはまります。周期の長さが素数だと、データの中の規則的なパターンと共鳴しません。もう1つの大きな用途は暗号で、非常に大きく互いに離れた素数から鍵を組み立て、その積を元の2つの素数に戻すのがどれほど難しいかに安全性が載っています。小さな用途はそこかしこにあります。割り切れるという主張の確認、ある数が2つの素数の積かどうかの検査、そして双子素数や連続する素数の間隔についての古典的なパズルです

このページはどうやって判定していて、どれくらい確かですか

約数を数えることで、これは確率的ではなく厳密です。ある数が素数であるのは正の約数をちょうど2つ持つときでそのときに限るので、個数は間違える余地なく問いを決着させます。騙されるかもしれない判定を信用する必要もありません。数え上げは平方根までの試し割りで行うので、100万が上限になります。それを超えると方法が不正確になるのではなく遅くなるからです。ずっと大きな数では厳密な方法は本当に実用的でなくなり確率的な判定が使われますが、この大きさでは確実さより劣るものを甘受する理由はなく、このページもそうしていません

判定だけでなく約数の個数まで表示するのはなぜですか

個数が判定の理由であり、それを見せれば両者が食い違えなくなるからです。バッジは二度目の計算ではなく、隣に印字された数を読んだものです。それ自体も役に立ちます。個数が奇数ならその数は平方数です。平方根が別の約数ではなく自分自身と組になるからです。個数が2ならそれが素数の定義です。数の大きさの割に個数が多ければ小さい因数をたくさん持つということで、約数を速く集める手の数のことです。そしてこのページをほかのページとつなぎます。素因数分解のページは同じ入力に対して同じ約数の個数を報告し、指数からそれを求めます。だから2つのページは互いを検算し合っています

• Prime Number — 定義と約数の個数による判定、そして1がそこから除かれる理由 — Wolfram MathWorld (United States)
• Prime Gaps — 連続する素数の間隔と、100万の近所がどうなっているか — Wolfram MathWorld (United States)
• Composite Number — 素数の補集合と、1がどちらの仲間でもない理由 — Wolfram MathWorld (United States)
• 学習指導要領（平成29・30・31年改訂） — 素数と合成数が小学校高学年の「数と計算」領域で扱われることを示す文部科学省の告示・解説 — 文部科学省