에라토스테네스의 체를 이용한 특정 수까지의 소수 집합 구하기

프로그래머스에서 애증의 코딩테스트...를 준비하는 도중 1단계 문제임에도 성능때문에 계속 실패하는 문제에 부딪혔다.

 

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

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

 

소수를 구하는 함수를 짠 후, 모든 숫자에 대해 소수인지 판별하여 카운팅을 하는 방식으로 짯더니 실패.

 

검색결과 에라토스테네스의 체를 사용하여 구하여야 1부터 아주 큰 수 까지의 숫자 중에서 소수의 집합을 구할 때 효율적이라고 한다.

 

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부터 1씩 증가시키며 2배수 이상의 숫자들을 지워준다. 이미 지워진 숫자는 건너 뛴다. 아래는 자바스크립트로 짠 코드

 

function solution(n) { 
    let arr = [] 
    // 1은 소수가 아니고, 2부터 소수가 될 수 있으므로, 2부터 구하고자 하는 값까지의 배열을 만든다. 
    for (let i = 2; i <= n; i++) { 
        arr[i] = i 
    } 
    // 2부터 시작해서 2배수 이상의 숫자를 모두 지우되, 이미 지워진 숫자는 건너 뛴다. 
    for (let i = 2; i <= n; i++) { 
        for (let j = i + i; j <= n; j += i) { 
            if (arr[j] === 0) { 
                continue 
            } 
            arr[j] = 0 
        } 
    } 
    return arr.filter((item) => item !== 0).length 
}