프로그래머스) 소수 찾기

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

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

 

나의 풀이

테스트는 통과하는데 효율성 테스트에서 계속해서 광탈하였다..

그러던 중 에라토스테네스의 체라는 '소수를 찾는 방법'을 알게 되어 효율성 테스트에서도 통과할 수 있었다.

 

에라토스테네스의 체의 알고리즘은 위키에서 확인할 수 있다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

간단히 요약하자면 소수인 2, 3, 5, 7의 가장 낮은 수(즉 2, 3, 5, 7)을 제외한 배수들을 없애면 소수만 남게 된다는 것이다.

또한 주어진 숫자 n의 제곱근보다 작은 수의 배수만 제거하면 충분하다(약수의 대칭성 때문).

 

function solution(n) {
    const numArr = [];
    
    for (let i = 0; i <= n; i++) {
        if (i === 1) {
            numArr.push(0);
            continue;
        }
        
        numArr.push(i);
    }
    
    for (let i = 2; i <= Math.sqrt(n); i++) {
    	if (!numArr[i]) {
            continue;
        }
        
        for (let j = i + i; j  <= n; j += i) {
            numArr[j] = 0;
        }
    }
    
    return numArr.filter(num => num).length;
}

먼저 n까지의 숫자 배열을 생성하고, Math.sqrt(n)으로 제곱근까지 반복문을 진행하고,

반복문을 중첩하여 i의 배수를 순회하며 값을 0으로 재할당한다.

그리고 filter를 사용하여 0이 아닌 수만 걸러내고 배열의 길이로 반환하였다.

 

나는 n까지의 배열을 만들고 소수의 배수를 지워 나가는 것이 비효율적이라고 생각했다.

그러나 구간이 정해져 있는 경우 에라토스테네스의 체 알고리즘만큼 효율적이고 빠른 알고리즘은 없다고 한다!

 

다른 사람의 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

같은 원리를 사용했지만 이 분은 Set 객체를 활용하셨다.

Set 객체는 자료형에 관계없이 primitive, reference 값 모두 유일한 값을 저장할 수 있다.

그리고 Set의 내장 메서드인 add, delete, size를 사용하여 값을 제거하였다.