에라토스테네스의 체

프로그래머스 소수찾기 문제를 풀면서 예전에 사용해보았던 에라토스테네스의 체라는 알고리즘을 다시 한 번 사용해보았습니다.

에라토스테네스의 체를 그림으로 한번 살펴볼까요?

출처: 위키백과

이런 식으로 2의 배수부터 지워나가 3의 배수, 4의 배수... 증가시켜 제거하는 방법입니다. 

코드 리뷰를 통해서 확인해보겠습니다.

function solution(n) {
    let arr = Array(n+1).fill(true).fill(false,0,2); 
    //n의 숫자의 크기만큼 array를 할당해주고 true로 채워줍니다. 0,1은 소수가 아니기 때문에 제외해줍니다. 
    
    for(let i =2; i*i<=n;i++){ //i의 배수만큼 증가시켜줍니다. *(2는 소수임으로 2를 제외한 2의배수부터 증가시킵니다.) 
        if(arr[i]){ //arr[i]가 참일 경우
            for(let j=i*i;j<=n; j+=i){ //제곱값만큼 배열값을 찾아 제외해줍니다.
                arr[j] = false;
            }
        }
    }
    return arr.filter(e => e).length; //true인 경우만 소수임으로 false을 제외해줍니다.
}

오래간만에 에라토스테네스의 체를 사용해서 문제를 풀어보았습니다.