[LeetCode] 204. Count Primes

😎풀이

1. n의 길이를 갖는 배열 생성
2. n의 제곱근까지 순회
   2-1. i가 소수라면, i의 배수는 모두 소수가 아님
3. 남은 소수 카운트
4. 카운트 결과 반환

function countPrimes(n: number): number {
    let count = 0
    const isPrime = new Array(n).fill(true)
    isPrime[0] = false
    isPrime[1] = false
    // 에라토스테네스의 체 특성 상 n의 제곱근 까지만 확인하면 됨
    for(let i = 2; i * i < n; i++) {
        if(isPrime[i]) {
            // i가 소수라면, i의 배수들은 모두 false
            for(let j = i * i; j < n; j += i) {
                isPrime[j] = false
            }
        }
    }
    // 남아있는 소수 카운트
    for(let i = 2; i < n; i++) {
        if(isPrime[i]) count++
    }

    return count
};