次の素数を求める計算

整数を入力すると、それより大きい最小の素数、それより小さい最大の素数、二つの差、そして続く10個の素数を返します。10^24 までの数に対応し、正確な整数演算を使うので、1兆や 10^18 の次の最初の素数も求められます。

使い方

1. 数を入力します。カンマ、1e12、10^12 のどれも使えます。
2. 入力した数が素数のときにその数自身を答えにしたい場合は、チェックボックスをオンにします。
3. 次の素数、前の素数、差を確認します。
4. 表で、続く10個の素数とそれぞれの差を見ます。

計算式

次の素数(n) = p > n を満たす素数 p のうち最小のもの

n + 1、n + 2、… を順に調べます。各候補はまず1,000未満の素数で割り、残ったものは13個の素数 2、3、5、…、41 を底とするミラー–ラビン判定にかけます。この底の組は 3.3 × 10^24 未満のすべての数で誤判定がないことが証明されているため、答えは「おそらく素数」ではなく確実な素数です。ベルトランの仮説により、1より大きいどの n についても n と 2n の間に素数があります。

計算例

1,000,000 の次の素数は 1,000,003 です。1,000,001 = 101 × 9,901 で、1,000,002 は偶数だからです。前の素数は 999,983 で、入力した数から次の素数までの差は 3 です。1,000,000,000 の次の素数は、プログラマがよく使う法 1,000,000,007 です。