🧮

Count Primes

보통 알고리즘 +20pts

Problem

Write a function that counts prime numbers less than n.

Examples

Input: countPrimes(10)

Output: 4

💡 2, 3, 5, 7

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 ...

View detailed explanation →

Key Concepts

에라토스테네스의 체 소수 세기 배열 초기화 최적화

Time: O(n log log n) Space: O(n)

solution.js

Ctrl + Enter

Run tests to see results here.