[알고리즘] 에라토스테네스의 체

에라토스테네스의 체

• 소수를 판별하는 알고리즘
• 소수들을 대량으로 빠르고 정확하게 구해내는 방법

단일 숫자 소수 여부 확인

• 어떤 수의 소수 여부를 확인할 때는 특정한 숫자의 제곱근 약수의 여부를 검증하면 O(N*1/2)의 시간 복잡도로 빠르게 구할 수 있음
• 수가 수(N)을 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N의 제곱근 이하이기 때문

원리

1. 가장 먼저 소수를 구할 범위만큼 배열을 할당한 후 초기화
2. 2부터 시작하여 특정 수의 배수에 해당하는 수를 모두 지우기(지울 때 자기 자신은 건너뛰기)
3. 이후 남아있는 수들 출력

보다 쉬운 이해를 위해 예제 이미지를 첨부하겠다.

코드

에라토스테네스의 체를 이용하여 소수의 개수를 구하는 코드는 다음과 같다

function solution(n) {
		//수만큼 배열을 만들고 1로 채우기
    let arr = Array(n+1).fill(1);
		//쓰지 않을 0번째와 숫자 1은 0으로 바꿔두기
    arr[0] = 0;
    arr[1] = 0;
    //for문과 while을 활용하여 소수가 아닌 것들은 0으로 전환
    for(let i = 2; i < n; i++){
        let j = 2;
        while(i*j <= n){
            arr[i*j] = 0;
            j++;
        }
    }
		//filter를 사용하여 1(참)인 것들의 길이 반환
    return arr.filter((e) => e).length;
}

출처: https://ko.wikipedia.org/wiki/에라토스테네스의_체