[ 프로그래머스 / JS ] Lv.1 소수 찾기

 

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

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

---

제한사항

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

---

풀이

function solution(n) {
    let arr = new Array(n - 1).fill(2).map((ele, idx) => ele += idx);

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 0) continue;
        
        for (let j = i + arr[i]; j <= n; j += arr[i]) {
            arr[j] = 0;
        }
    }
    
    return arr.filter(ele => ele).length
}

실행에 걸린 최대 시간 : 102.07ms

 

사고과정

1. 에라토스테네스의 체를 쓰자!

 

평가

 

개선점

 

알게된점

1. 에라소트테네스의 체