프로그래머스 - 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

---

내 코드

function solution(n) {
    let arr = Array(n+1).fill(true).fill(false,0,2); //기준 배열
    
    for (var i=2; i * i <= n; i++){
        if(arr[i]) {
            for(var j = i * i; j <= n; j+=i){
                arr[j] = false; //배수 제거 
            }
        }
    }
    let cnt = arr.filter(pCnt => pCnt === true).length;
    return cnt;
}

소수의 판별과 같은 경우 에라토스테네스의 체 알고리즘을 통해 구할 수 있다.

에라토스테네스의 체
위 블로그에 자세히 친절하게 설명이 되어 있어 참고하기 좋다.