[프로그래머스 level1] 소수찾기

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

문제 풀이

이론

문제에서 n은 2이상 1000000이하의 자연수인데, 이 경우 최대 1000000일 때 O(n)의 시간복잡도를 통과하지 못할 수 있다. 따라서 시간복잡도가 O(n) 이하가 되도록 O(√n) 혹은 O(log N)의 시간복잡도를 가져야한다. (시간복잡도 노트 정리 참고)
단순하게 접근하면 시간복잡도가 무조건 넘기 때문에, 에라토스테네스의 체의 원리를 이용해서 소수를 빠르게 구할 수 있다.O(√n)의 시간복잡도를 가진다.
에라토스테네스의 체의 원리란, 만약 n=16이라고 가정하자. 즉 나는 2~16사이의 소수를 찾고싶다.(1은 소수아니니까 제외!)
2를 제외한 2의 배수를 삭제한다.(단, 범위는 10까지)
[4, 6, 8, 10, 12, 14, 16]

3을 제외한 3의 배수를 삭제한다.
[6, 9, 12, 15] (이미 6, 12은 위에서 삭제됨)

4를 제외한 4의 배수를 삭제한다.
[8, 12, 16] (이미 8은 위에서 삭제됨)

5를 제외한 5의 배수를 삭제한다.
이미 다 삭제됨
10은 5의 배수이면서 2의 배수이다
15는 5의 배수이면서 3의 배수이다.
즉, 25(5^2)이 나오기 전까지의 모든 5의 배수는 이미 삭제되었다.

즉, √16 = 4까지만 검사하면 된다. 4이후 배수들은 모두 삭제되었기 떄문에 신경쓰지 않아도 된다.
코드에서는 i<√n대신, i^2<n과같이 작성하면 된다.

코드

function solution(num){
    let arr=Array.from({length:num+1}, ()=>1);
    arr[0]=0, arr[1]=0; //0, 1은 소수가 아니다(제외)
    
    for(let i=2; i*i<num; i++){
        //아직 지워지지 않았을 때
        if(arr[i]){
            for(let j=i*i; j<=num; j+=i){
                arr[j]=0; //지움(소수 아님)
            }
        }
    }
    //지워지지 않은 것 (값이 1인것)
    return arr.filter(v => v===1).length;
}

앞으로 n까지 범위 내에서 소수의 갯수를 구해야한다면, 에라토스테네스의 체를 사용해서 풀이하자. 풀이방법 외우기!
그리고, arr에서 값이 1인 것의 개수를 구하기 위해 filter를 통해 value===1인 것을 골라내고 이것의 길이를 구했다. for문으로 단순하게 cnt++ 해줄수도 있지만, for문은 넘 길다... for문이 더 단순해서 빠르지만, filter도 빠른편이니까 사용해도 괜찮다.

참고

javascript 배열에서 특정 값의 개수 구하기

https://hianna.tistory.com/488

for, foreach, filter, map, reduce의 성능 비교

https://daesuni.github.io/Loop-performance/