C - Find Prime

連続する正整数がすべて合成数で、素数が全くないような場所は素数砂漠 (prime gaps) と呼ばれます。 $n-1$ 個の連続する合成数の列を、長さ $n$ の素数砂漠ということにします。

実は、どんな大きい正整数 $k$ に対しても、長さ $k$ 以上の素数砂漠が存在することが示せます（たとえば $(k+1)!+2, (k+1)!+3, \cdots, (k+1)!+k+1$ は長さ $k$ 以上の素数砂漠になる）。

しかし、小さい自然数においては素数砂漠は実はそれほど長くなく、$10^9$ 以下で最大長さ $282$、$10^{18}$ 以下でも最大長さ $1442$ であることが知られています ( https://arxiv.org/pdf/1309.4053.pdf )。

よって、$i=L,L+1,L+2,\cdots, R$ の順に（整数 $N$ に対して $O(\sqrt{N})$ 時間で動く）素数判定を行い、素数だったら出力して終了する一見愚直なコードが間に合います。