次の素数の探索範囲の上界について
主張
$ p_nが$ n番目の素数なら，$ n+1番目の素数$ p_{n+1}は$ p_n!+1以下に存在する． 証明
$ p_n!+1の1ではない最小の約数を$ mとする．
$ p_n < m \leq p_n!+1が成り立つ．
$ p_n < m
階乗の定義より，$ p_n!+1は2以上$ p_n以下のいかなる数で割っても1余る．
割り切れたとしたら$ p_n+1以上の数で割っている．
$ m \leq p_n!+1
約数の定義より自明．
$ mは素数である．
$ p_n!+1は$ p_n以下の素数で割り切れないのだから，当然その約数も$ p_n以下の素数で割り切れない．
よって，$ mは$ p_{n+1}番目の素数である．❏