모든 챌린지
쉬움 0명 해결 정답률 0%

구간 내 소수의 개수

두 경계값을 모두 포함하는 구간 안에 소수가 몇 개 있는지 셉니다.

배우게 될 내용

  • 체로 합성수를 표시할 수 있다
  • 구간 안에서 표시된 값을 셀 수 있다
  • 빈 구간과 0, 1을 처리할 수 있다

문제

원문 보기 (영어)

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

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.