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

 

에라토스테네스의 체

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

어떤 수의 소수의 여부를 확인 할 때는 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

 

 

2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고.. 주어진 수의 제곱근까지만 확인해보면 끝난다. >> 이거였어!!!

[출처] https://velog.io/@cjy0029/%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

 

---

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고 이후에 하나씩 지워나가는 방법을 이용한다.

1. 목록 생성: 먼저, 2부터 원하는 최대 숫자까지의 모든 숫자를 나열
2. 최소 수 찾기: 아직 체크하지 않은 가장 작은 숫자를 찾습니다. 이 숫자는 소수
3. 소수의 배수 제거: 방금 찾은 소수의 모든 배수를 목록에서 제거
4. 반복: 더 이상 제거할 배수가 없을 때까지 이 과정을 반복

---

예시) 숫자 n까지의 모든 소수 찾기 

function sieveOfEratosthenes(n) {
    let isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {// i가 소수인 경우
            // i의 배수들을 소수 목록에서 제거
            for (let j = i * 2; j <= n; j += i) {
                isPrime[j] = false; // i의 배수를 소수에서 제외
            }
        }
    }

    // 결과적으로 소수인 인덱스만 반환
    let primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }
    return primes;
}

// 30까지의 소수를 출력
console.log(sieveOfEratosthenes(30));