문제
1부터 100까지 소수는 몇 개일까요? 50부터 60까지는요? low ≤ p ≤ high를 만족하는 소수 p의 개수를 세세요. 0과 1은 소수가 아니라는 점을 잊지 마세요. high까지 체를 만들어 두면 빠르게 답할 수 있습니다.
count_primes_in_range(low, high) 함수를 구현하세요.
입력
low: 구간의 아래쪽 경계이며 구간에 포함됩니다.
high: 구간의 위쪽 경계이며 구간에 포함됩니다.
출력
구간 안에 있는 소수의 개수를 반환합니다. low > high이면 빈 구간이므로 답은 0입니다.
제약 조건
0 ≤ low ≤ 1,000,000
0 ≤ high ≤ 1,000,000
예시
입력:
low = 1
high = 100
예상 출력:
expected = 25
입력:
long long low = 1;
long long high = 100;
예상 출력:
long long expected = 25;
입력:
long low = 1;
long high = 100;
예상 출력:
long expected = 25;
설명
100 이하의 소수는 2, 3, 5, … 97까지 25개이므로 답은 25입니다.
입력:
low = 50
high = 60
예상 출력:
expected = 2
입력:
long long low = 50;
long long high = 60;
예상 출력:
long long expected = 2;
입력:
long low = 50;
long high = 60;
예상 출력:
long expected = 2;
설명
50과 60 사이의 소수는 53과 59뿐이므로 답은 2입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
high까지 체를 만들고, 각 소수의 배수를 그 소수의 제곱부터 지워 나가세요.
힌트 2
그다음 low부터 high까지 소수로 남아 있는 수를 세세요.
힌트 3
low가 high보다 크면 계산할 것이 없습니다.
예상 복잡도
시간 O(high log log high), 추가 공간 O(high)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.