1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)
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;
}
소수의 판별과 같은 경우 에라토스테네스의 체 알고리즘을 통해 구할 수 있다.
에라토스테네스의 체
위 블로그에 자세히 친절하게 설명이 되어 있어 참고하기 좋다.