소수 세기

Prime Numbers 게랄트, Pixabay 제공

정수 $p$가 $1$보다 크고, 나머지 없이 나눌 수 있는 수가 $1$과 $p$뿐이면 이 정수를 소수라고 한다. 예를 들어, $10$은 나머지 없이 $1$, $2$, $5$, $10$로 나눌 수 있으므로 소수가 아니다. 반면, $11$은 나머지 없이 $1$와 $11$로만 나눌 수 있으므로 소수이다. 같은 방식으로 $2$, $3$, $17$은 소수이지만, $4$, $9$, $15$은 소수가 아님을 알 수 있다.

$1$부터 $100$까지의 수를 살펴보면, 그중 $25$개가 소수임을 알 수 있다. 조금 더 손으로 계산해 보면, $1$부터 $1\,000$까지 정확히 $168$개의 소수가 있다는 것을 알아낼 수 있다.

두 정수 $a$과 $b$가 주어질 때, $a$부터 $b$까지 소수가 몇 개 있는지 계산한다.

채점

그룹 | 점수 | 제한

1 | 19 | $b \leq 10^3$

2 | 23 | $b \leq 10^9$, $b-a \leq 10^3$

3 | 14 | $b \leq 10^{18}$, $b-a \leq 10^5$

4 | 13 | $b \leq 10^7$

5 | 16 | $b \leq 10^{15}$, $b-a \leq 10^7$

6 | 15 | $b \leq 10^{11}$

입력은 두 정수 $a$과 $b$가 있는 한 줄로 주어진다. ($1 \leq a \leq b$).

$a$부터 $b$까지의 소수의 개수를 출력한다.