소수 구하기 (feat.에라토스테네스의 체)

문제

오늘도 어김없이 난관에 봉착

프로그래머스 소수 찾기에서 효율성 통과에 어려움을 겪었다.

 

문제링크

 

 

시도

function solution(n) {
    let answer = 0;
    
    function isPrime(sum) {
    for (let i = 2; i <= Math.sqrt(sum); i++) {
        if (sum % i === 0) return false;
    }
    return true;
}
    
        for (let i = 2; i <= n; i++) {
            if(isPrime(i)) answer += 1
    };   
        
    return answer
}

소수 여부를 체크하는 함수를 추가하여 반복문을 돌렸다.

하지만 보기좋게 효율성 체크에서 탈락.....

좀더 간결한 코드가 필요하다.

구글링을 하던 중 

'에라토스테네스의 체'라는 방법을 발견했다.

 

해결

function solution(n) {
    let answer = 0;
    const arr = new Array(n+1).fill(true);
      
    for(let i = 2; i <= n; ++i){
        // 이미 소수가 아닌 인덱스는 건너뛴다.
        if(arr[i] === false){
            continue; 
        }
        // 배수는 소수가 아니라 0으로 설정
        for(let k = i * 2; k <= n; k += i){
            arr[k] = false;
        }
    }   
    
    return arr.filter(a => a === true).length - 2;
}

n 길이 만큼의 배열을 만들어서 각 요소를 true로 채운다.

에라토스테네스의 체를 토대로 반복을 돌린다.

반복을 돌리면서 i의 배수를 만들어 놓은 배열에서 false로 바꿔 나간다.

반복이 끝나면 filter로 true 값을 걸러서 길이를 구한다.

마지막으로 2를 빼주면 (0과 1) 완성이다.

 

 

알게된 것

소수는 1과 자기 자신외에는 나누어 떨어지는 수가 없는 숫자들이다.

보통은 반복문을 돌려 체크를 하지만 숫자가 커질 경우에는 효율성이 매우 떨어지는 것을 확인했다.

그래서 에라토스테네스의 체를 참고하여 코드를 수정했다.

에라토스테네스의 체는 2부터 소수를 구하고자 하는 구간의 숫자를 모두 나열한 뒤

나열한 수 중에 가장 작은 수를 제외하고 그 수의 배수들을 차례로 지워나가는 방법이다.

그렇게 되면 최종적으로 해당 구간의 소수들만 남게 된다.