문제설명

• 1부터 n사이에 있는 소수의 개수를 반환하는 함수 작성
• 소수는 1과 자기 자신으로만 나누어지는 수

제한조건

• n은 2이상 1000000이하의 자연수

풀이

function solution(n) {
    let answer = 0;
    let array = Array(n+1).fill(true).fill(0,2,false);
    /*array[0] = false;
    array[1] = false;*/
    for(let i=2;i*i<=n;i++){
        if(array[i]){
            for(let j=i*i;j<=n;j+=i){
                array[j] = false;
            }
        }
    }
    console.log(array);
    answer = array.filter(e=>e).length;
    return answer;
}

체크포인트

• 에라스토스테네스의 체 활용
• 2~n까지의 수 중 2부터 n의 제곱근까지의 소수의 배수들을 제외시키면 소수만 남는다
• Array(n+1).fill(true).fill(0,2,false);: 0과 1은 소수가 아니므로 false
• let i=2; i*i<=n; i++: i부터 n의 제곱근까지의 범위
• let j=i*i; j<=n; j+=i: 소수의 배수를 찾아 모두 false