前の素数を求める計算

このツールは前の素数、つまり入力した数より小さい最大の素数を求めます。ハッシュテーブルの大きさを決めるとき、素数の間隔の宿題を確認するとき、2のべき乗や10のべき乗のすぐ下にある素数を法に選ぶときなどに便利です。24桁までの整数を正確に扱い、入力した数のすぐ下にある10個の素数も一覧にします。

使い方

1. 2より大きい整数を入力します。カンマも使えるので 1,000,000 でも構いません。
2. 前の素数と、入力した数よりどれだけ小さいかを確認します。
3. 入力した数自身が素数かどうかを確認します。
4. 表で、さらに下にある素数を見ます。

計算式

prevprime(n) = max { p は素数 : p < n }

n − 1 から偶数を飛ばしながら下に数えて、各候補を調べます。候補が底 2、3、5、…、41 のミラー–ラビン判定に合格すれば素数です。この13個の底を使うと、約 3.3 × 10²⁴ 未満のすべての数で誤判定がないので、答えは確率的ではなく確実です。

計算例

n = 1,000,000 のとき、999,999（3で割り切れる）、999,997（= 757 × 1,321）と順に調べ、最初に見つかる素数 999,983 で止まります。差は 1,000,000 − 999,983 = 17 です。さらに下の素数は 999,979 と 999,961 です。