7095 : 연속 소수 구간
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 자연수 L과 R이 주어졌을 때, L 이상 R 이하의 닫힌 구간 [L, R]에 존재하는 소수의 개수를 구하는 프로그램을 작성하십시오.
L, R의 크기는 매우 크지만, 구간의 길이(R - L)는 최대 1,000,000으로 비교적 작습니다.
[제약 조건]
• 구간 $L, R$: $1 \le L \le R \le 10^{12}$, $R - L \le 1{,}000{,}000$
L, R의 크기는 매우 크지만, 구간의 길이(R - L)는 최대 1,000,000으로 비교적 작습니다.
[제약 조건]
• 구간 $L, R$: $1 \le L \le R \le 10^{12}$, $R - L \le 1{,}000{,}000$
입력 설명
첫째 줄에 $L$과 $R$이 공백으로 구분되어 주어집니다. ($1 \le L \le R \le 10^{12}, R - L \le 10^6$)
출력 설명
구간 $[L, R]$ 내의 소수 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
구간 체(Segmented Sieve) 알고리즘을 사용합니다. √R 이하의 소수들을 미리 체로 구한 다음, 이를 사용해 [L, R] 구간의 배수를 지웁니다.