5096 : 구간 소수

시간 2.000s · 메모리 256MB · 제출 20 · 정답 1

코드제출 문제 풀기

채점기록 통계 묻고답하기

구간 $[L, R]$ 에 포함된 소수의 개수를 구하십시오.

[제약 조건]
• $1 \le L \le R \le 10^{12}$
• $R - L \le 500000$
• 입력되는 모든 값은 정수입니다.

두 정수 $L, R$ 이 주어집니다.

소수의 개수를 출력하십시오.

1 10

구간 체(Segmented Sieve)를 사용하여 $\sqrt{R}$ 까지의 소수로 구간을 선별하십시오.