[프로그래머스] Javascript : 소수 찾기 (+에라토스테네스의 체)

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

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

입출력 예

 

나의 풀이

function solution(n) {
    let result = 0
    for (let i = 2; i <= n; i++) {
        if (i % 2 != 0) {
            result++
        }
    }

    return result
}

는 코드 실행했을 땐 테스트 통과가 됐지만 제출 후 체점의 경우엔 단 하나도 맞지 않았다.
그럼 어떻게 접근해야 하는지 생각해봤더니 for문을 계속 돌리면서 소수의 숫자는 지워야 했다.
그러다가 알게된 에라토스테네스의 체라는 알고리즘을 발견했다.

에라토스테네스의 체

: n까지의 수에서 소수만을 골라내는 알고리즘으로 _시간 복잡도_는 O(N log(logN)) 이다.
실행 방법은 주어진 n까지의 n의 배수들을 지워버리는 방법이다.

최종 코드

function solution(n) {
    // index[0]이 존재하므로 배열을 num + 1로 선언
    let arr = Array(n + 1).fill(true)

        // 0과 1은 소수가 아님 => false 처리
    arr[0] = false
    arr[1] = false

        // 제곱근까지만 반복
    for(let i = 2; i * i <= n; i++) {
        if(arr[i]) {
            for(let j = i * i; j <= n; j += i) {
                // 배수라면 소수가 아님 => false
                                arr[j] = false 
            }
        }
    }

        // true 값만 출력
    return arr.filter(el => el).length
}

 

다른 사람 풀이

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
}