Count Primes Explanation

Problem Summary

Write a function that counts prime numbers less than n.

Detailed Explanation

이 문제는 **에라토스테네스의 체(Sieve of Eratosthenes)**로 소수를 세는 방법을 학습합니다. ## 핵심 개념: 에라토스테네스의 체 범위 내 모든 소수를 효율적으로 찾는 고대 알고리즘입니다. ### 알고리즘 1. 2부터 n까지 모든 수를 소수로 가정 2. 2부터 시작하여 소수의 배수를 모두 제거 3. 제곱근까지만 반복 ### 코드 분석 ```javascript const isPrime = new Array(n).fill(true); isPrime[0] = isPrime[1] = false; for (let i = 2; i * i < n; i++) { if (isPrime[i]) { for (let j = i * i; j < n; j += i) { isPrime[j] = false; } } } ``` ### 시각화 (n=10) ``` [F, F, T, T, T, T, T, T, T, T] // 초기 (0,1은 F) [F, F, T, T, F, T, F, T, F, T] // 2의 배수 제거 [F, F, T, T, F, T, F, T, F, F] // 3의 배수 제거 결과: 2, 3, 5, 7 → 4개 ``` ### 최적화 - i * i부터 시작 (작은 배수는 이미 제거됨) - 제곱근까지만 확인 시간복잡도 O(n log log n)으로 매우 효율적입니다.

Solution Code

solution.js

function countPrimes(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j < n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime.filter(Boolean).length;
}

Key Concepts from This Problem

1. 에라토스테네스의 체

2. 소수 세기

3. 배열 초기화

4. 최적화

Common Mistakes

✗ i * i < n 조건을 i < n으로 하면 비효율적입니다

✗ j = i * i부터 시작하는 이유를 이해해야 합니다

✗ 0과 1을 false로 초기화하는 것을 잊지 마세요

Hints

Hint 1: 에라토스테네스의 체를 사용하세요.

Complexity Analysis

Time Complexity

O(n log log n)

Space Complexity

O(n)

Uses memory proportional to input size

Related Tags

#알고리즘 #소수 #에라토스테네스