[프로그래머스] Lv1) 소수 찾기 ( 에라토스테네스의 체, 소수 찾기 )

 

 

1 부터 n 까지의 수 중에서 소수의 개수를 반환하는 문제 입니다

이전  Lv1) 기사단원의 무기 문제에서 사용한 에라토스테네스의 체를 다시 이용하면 됩니다.

 

function solution(n) {
// idx 자체를 값으로 사용하기 위해 
    let isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

// 제곱근 까지만 계산 
    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // i의 배수들을 모두 false로 표시
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.filter(e => e === true).length;
}

 

제곱근 까지만 계산하는 이유는 아래 링크에 설명 되어있습니다.

https://daunje0.tistory.com/135

[프로그래머스] Lv1) 기사단원의 무기 ( 에라토스테네스의 체, 소수 , 약수 찾기 )