次の素数を求める仕組み

数列の中で入力値より後の最初の素数を示す図

0以上の整数nを入力すると、nより厳密に大きい最初の素数pを求めます。結果にはpとの差と、実際に判定した奇数候補の個数も表示されます。

「次」は入力値を含まない

p = \min \{q \in \mathbb{P} \mid q > n\}

条件はq > nです。nが17のような素数でも17は返さず、答えは19になります。左右の距離を比べる「最も近い素数」とは別の問題です。

探索はn + 1から始まります。2より小さい場合は2を採用します。2を過ぎた後は偶数がすべて合成数なので、奇数だけを候補にできます。

奇数候補については、その平方根まで割り切れる数がないか確認します。合成数なら少なくとも一方の因数が平方根以下にあるため、この範囲で約数が見つからなければ素数です。

n = 0ではp = 2、差は2です。n = 1でもp = 2ですが差は1になります。どちらも候補は1個です。

n = 14では、まず15を調べます。15は3で割り切れるため不採用です。次の17は素数なので、答え17、差3、候補2個になります。

n = 1000では1001、1003、1005、1007、1009を順に調べます。最初の4つは合成数で、1009が素数です。差は9、候補は5個です。

入力範囲は0から1,000,000,000,000までの整数です。上限を入力すると答えは1,000,000,000,039、差は39、奇数候補は20個になります。上限は入力nに対するもので、結果pは少し上回ることがあります。

この範囲では丸めや確率的な判定を使いません。小数、負の数、空欄は受け付けません。何百桁もの整数には別の大整数用アルゴリズムが必要です。

入力値が素数の場合と、偶数を飛ばす理由を押さえると結果を確認しやすくなります。

なりません。入力値より大きいことが条件です。17を入力した場合は19を返します。

いいえ。小さい側は比較せず、大きい側にある最初の素数だけを探します。

素数には正の約数がちょうど2個必要です。1の正の約数は1だけなので、次の素数は2です。

2以外の偶数はすべて合成数なので、探索中は飛ばし、候補数にも入れません。

はい。上限は入力値に適用されます。上限入力の次の素数は1,000,000,000,039です。

指定範囲では平方根までの約数を正確に調べるため、結果は確定した素数です。

同じトピックに関する次の計算機が役立つかもしれません：

気に入ったら、計算機をソーシャルメディアプラットフォームで共有してください。あなたにとっては簡単で、プロジェクトのプロモーションにとっては有益です。ありがとうございます！

差 p - n	1
調べた奇数候補	1