자바스크립트로 에라토스테네스의 체 구현하기 — 1부터 n까지의 소수 찾기

문제 개요

숫자 하나(n)를 매개변수로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 1부터 n 사이에 존재하는 모든 소수를 담은 배열을 반환해야 합니다.

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스 수학자 에라토스테네스가 고안한 고전적인 알고리즘으로, 특정 범위 안의 모든 소수를 매우 효율적으로 찾을 수 있습니다. 기본 원리는 소수의 배수들을 차례대로 걸러 내면, 마지막에 남는 수들이 곧 소수라는 것입니다.

알고리즘 접근 방법

1단계: 불리언 배열 초기화

먼저 주어진 숫자 크기만큼의 배열을 만들고 모든 값을 true로 초기화합니다. 배열의 각 인덱스는 소수 후보를 의미하며, 처음에는 모든 수가 소수라고 가정하는 것입니다.

2단계: 소수의 배수 제거

그다음 2부터 주어진 숫자의 제곱근(√n)까지 반복하는 for 루프를 실행합니다. 임의의 두 정수의 곱은 정의상 소수가 될 수 없으므로, 각 수의 배수를 모두 false로 표시해 제거합니다. 0과 1은 소수가 아니므로 미리 false로 처리해 둡니다. 제곱근까지만 확인해도 충분한 이유는, n보다 작은 합성수는 반드시 √n 이하의 약수를 가지기 때문입니다.

3단계: 소수 추출

마지막으로 여전히 true로 남아 있는 값들만 필터링하면, 해당 인덱스들이 바로 1부터 n 사이의 모든 소수입니다.

구현 예제

const num = 100;
const findPrimes = (num = 10) => {
    // num + 1 크기의 배열을 만들고 모든 값을 true로 초기화
    const numArr = new Array(num + 1);
    numArr.fill(true);
    // 0과 1은 소수가 아니므로 false 처리
    numArr[0] = numArr[1] = false;
    // 2부터 √num까지 반복하며 각 수의 배수를 제거
    for (let i = 2; i <= Math.sqrt(num); i++) {
        for (let j = 2; i * j <= num; j++){
            numArr[i * j] = false;
        }
    }
    // true로 남아 있는 인덱스만 모아 소수 배열 생성
    return numArr.reduce((acc, val, ind) => {
        if(val){
            return acc.concat(ind);
        }else{
            return acc;
        };
    },[]);
};
console.log(findPrimes(num));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
    2, 3, 5, 7, 11, 13, 17, 19,
    23, 29, 31, 37, 41, 43, 47, 53,
    59, 61, 67, 71, 73, 79, 83, 89,
    97
]

시간 복잡도

에라토스테네스의 체의 시간 복잡도는 O(n log log n)으로, 각 숫자마다 일일이 나눗셈을 검사하는 방식(O(n√n))보다 훨씬 빠릅니다. 따라서 큰 범위의 소수를 한꺼번에 구해야 하는 상황에서 특히 유용하게 활용할 수 있는 알고리즘입니다.