소수 간극
소수 간극 (Prime Gap) $g_{n}$은 다음과 같이 정의합니다.
$$
g_{n} = p_{n + 1} - p_{n}
$$
$p_{n}$은 $n$번째 소수 입니다.
$p_{n} < 100000000 = 10^{8}$일 때에는 $g_{n} < 222$임이 알려져있고, $p_{n} < 2^{31}$일 때에는 $g_{n} < 294$임이 알려져있습니다. (즉, int 범위에서는 아무 수 $K$를 골라도 $K \pm 147$ 안에 소수 하나쯤은 있는 셈입니다.)
또, $p_{n} < 2^{63}$일 때에는 $g_{n} < 1512$임이 알려져 있으므로, 소수는 생각보다 굉장히 조밀하게 모여있음을 알 수 있습니다.
소수 간극에 대한 추측으로는 여러가지가 있는데, 가장 유명한 추측은 란다우 문제인 르장드르의 추측 이 있습니다.
소수 간극에 대한 특징 중 하나는 다음과 같습니다.
임의의 정수 $M$에 대해,
$$
g_{n} > M
$$
인 정수 $n$이 존재한다.
즉, 소수 간극이 1억인 경우도, 1조인 경우도, 1경인 경우도 존재한다는 것입니다.
이는 $(M + 2)! + 2$부터 $(M + 2)! + M + 2$까지의 모든 수가 합성수이므로 생기는 일입니다.
$(M + 2)! + K$ ($2 \leq K \leq M + 2$)는 각각 $K$의 배수입니다.