いろいろな素数が探索されていますが、ある自然数が素数かどうかを判定をすることは、かなりの計算量を必要とします。

そこで、素数かどうかの問題をすこし変えた、ある区間の間に素数があるのかないのかという問題もあります。

素数は無限に存在していますが、大きな数になってくるとそれが素数である率がだんだん減ってきます。

素数の存在を示す命題で、ルジャンドル予想というのがあります。

自然数nに対して、n^2と(n+1)^2の間に素数が存在する。

現在、これは未解決問題です(Wikipediaによる)。

似たような命題で、ベルトラン=チェビシェフの定理(以後単にチェビシェフの定理と呼ぶ)というがあります。


自然数nに対して、nと2nの間に素数が存在する。

チェビシェフの定理の方がルジャンドル予想より難しそうですが、
チェビシェフの定理は定理と呼ばれていることからもわかりますように、証明されています。