[프로그래머스] 230922 코딩테스트 연습

소수 찾기 (시간복잡도 고려해서) 

* 에라토스테네스의 체 : 

// 에라토스테네스의 체
function solution(n) {
    var answer = 0;
    
    function eratostenes(m) {
        // 0과 1은 소수에서 제외
        let arr = new Array(m+1).fill(true).fill(false, 0, 2);

        // i*i >>> 11^2가 120보다 큰 경우는 의미가 없다
        for(let i=2 ; i*i <= m ; i++) {
            if(arr[i]){
                for(let j=i*i; j<=m; j+=i) {
                    arr[j] = false; // 배수 제거
                }
            }
        }
        return arr;
    }
    
    let isPrimes = eratostenes(n);
    answer = isPrimes.filter(e => e).length;
    
    return answer;
}