에라토스테네스의 체 - 자바스크립트 구현

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 찾는 알고리즘 중 하나로, 고대 그리스의 수학자 에라토스테네스가 개발했다. 이 알고리즘은 주어진 범위 내의 모든 소수를 찾아내는 효율적인 방법을 제공한다.

 

 

 

 

 

에라토스테네스의 체 동작과정

① 초기화

- 2부터 시작해서 1부터 주어진 숫자(n)까지의 모든 수를 포함하는 리스트를 생성한다.

 

② 0, 1 제거

- 0과 1은 소수가 아니므로 제거하거나 제외한다.

 

③ 2의 배수 제거

- 0과 1의 다음 숫자인 2부터 시작한다. 2는 소수이므로, 2를 제외한 2의 배수들은 모두 제거한다.

 

④ 다음 소수 찾기
- 아직 제거되지 않은 가장 작은 수를 소수로 선택한다. 이를 편의상 p라고 칭한다.

 

⑤ p의 배수 제거

- p를 제외한 p의 배수들을 모두 제거한다.

 

⑥ 반복

- 리스트에 남아 있는 가장 작은 수를 다음 소수로 선택하고, 해당 소수의 배수를 제거한다. 이 과정을 반복하면 리스트에 남아 있는 수들은 모두 소수가 된다.

 

 

 

 

 

자바스크립트 코드 구현 ①

• 시간 복잡도 : O(n log log n)

에라토스테네스의 체는 반복이 진행될수록 소수의 배수들이 지워져 가므로, 남아 있는 수들은 소수임이 보장된다.

function sieveOfEratosthenes(limit) {
    // 초기화: 2부터 limit까지의 모든 수를 포함하는 배열 생성
    const primes = new Array(limit + 1).fill(true);
    primes[0] = primes[1] = false; // 0과 1은 소수가 아님

    // 에라토스테네스의 체 알고리즘 수행
    for (let i = 2; i <= Math.sqrt(limit); i++) {
        if (primes[i]) {
            // i의 배수들을 제외 (소수가 아닌 수로 표시)
            for (let j = i * i; j <= limit; j += i) {
                primes[j] = false;
            }
        }
    }

    // 소수만 남은 배열을 반환
    return primes.reduce((acc, isPrime, index) => {
        if (isPrime) acc.push(index);
        return acc;
    }, []);
}

// 예시: 50 이하의 소수 찾기
// 0과 1은 소수가 아니므로 제외한다.
const primesUpTo50 = sieveOfEratosthenes(50);
console.log(primesUpTo50); // 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

 

 

 

 

자바스크립트 코드 구현 ②

위 코드에서는 소수인 것만 골라냈다면, 아래 코드는 에라토스테네스의 체를 이용하여 합성수 인것만 골라내는 코드이다. 합성수란 약수의 개수가 3개 이상인 수를 의미한다. 즉, 합성수는 소수의 배수이면 전부 해당한다. 위 코드와 반대로 소수를 제외한 모든 수를 리턴한다.

function sieveOfEratosthenes(n) {
    // 초기화: 2부터 limit까지의 모든 수를 포함하는 배열 생성
    let dp = new Array(n+1).fill(1)
    
    // 에라토스테네스의 체 알고리즘 수행
    for(let i = 2 ; i <= n ; i++){
        if(dp[i]){
            for(let j = 2 ; i*j <= n ; j++){
                dp[i*j] = 0
            }
        }
    }

    return dp.reduce((acc, isPrime, index) => {
        // 소수가 아닌 수들의 배열을 반환
        if (!isPrime) acc.push(index);
        return acc;
    }, []);
}

// 예시: 0과 1을 제외한 50 이하의 소수가 아닌 수 찾기
const primesUpTo50 = sieveOfEratosthenes(50);
console.log(primesUpTo50);  // 출력 : [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50]