Count Primes
Coddy의 코딩 인터뷰 챌린지 - 팩 V 코스 레슨 — 3개 중 3번째.
챌린지
어려움정수 n을 입력받아 n보다 작은 소수의 개수를 반환하는 함수 countPrimes를 작성하세요.
참고: 시간 복잡도는 O(nlogn)보다 효율적이어야 합니다.
1 <= n <= 1000000
예시:
입력 - 10
예상 출력 - 4
설명 - 10보다 작은 소수는 4개가 있습니다: 2, 3, 5, 7
입력 - 13
예상 출력 - 5
설명 - 13보다 작은 소수는 5개가 있습니다: 2, 3, 5, 7, 11 - 13은 포함되지 않음에 주의하세요!
직접 해보기
int countPrimes(int n) {
// 여기에 코드를 작성하세요
}