[JS] 연습문제 - 소수 찾기

function solution(n) {
    let filterArr = [...new Array(n+1).keys()]

    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (filterArr[i]) {
            for (let j = i * i; j <= n; j += i) {
                filterArr[j] = false;
            }
        }
    }
    return filterArr.filter((x) => !!x === true).length - 1;
}

 

프로그래머스

코딩테스트 연습 - 소수 찾기

 

백준에서도 풀었던 소수 찾기 문제
에라토스테네스의 체를 기억하자
기억해야할 것

1. 주어진 숫자 n에 대해서 n의 제곱근보다 작거나 같은 수까지만 소수를 찾으면 된다. n의 제곱근보다 큰 소수의 경우에는 어차피 앞선 소수들로인해 본인 제곱인 애들부터 false로 바꾸게 되는데, 본인 제곱이 n보다 크다면 어차피 배열에 없는 숫자이기 때문
2. 각 소수의 제곱 이후의 배수들만 false 처리하면 된다.
   ex) 2 -> 2의 제곱인 4의 배수부터 전부 다 false 처리, 3 -> 만약 제곱수부터 안하면 6부터 false 처리해야하는데 자연스럽게 이전 소수인 2로 인해 6은 false 처리가 되어있다. 이런 식으로 소수 본인 제곱 이상의 배수들만 확인해주면 된다.
3. 배열의 길이와 아직 0과 1도 들어있다는 것을 기억해서 return 값을 조정해주자
   위의 경우에 filter 함수를 이용하여 값이 false인 값들을 처리(이 때, 0도 false이기 때문에 같이 처리), 결국 남은 배열에서 제거해줘야할 값은 1이 남아있다. 해서 length에서 -1 을 해준다.

[참고: 에라토스테네스의 체를 쉽게 설명](https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4) [참고 : 백준에서 풀었던 소수 찾기](https://jayden1116.tistory.com/599)