[Algorithm] 선형 에라토스테네스의 체(선형 체, Linear Sieve) : O(n)으로 소수 구하기!

 

🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)

 

 

 

 

 

⭐  선형 에라토스테네스의 체는 기존의 에라토스테네스의 체를 개선하여 $O(n)$의 시간 복잡도로 소수를 찾는 알고리즘이다.

이는 각 숫자를 가장 작은 소인수로 한 번만 처리하여 불필요한 계산을 줄였다.

 

 

 

에라토스테네스의 체에 대한 글

 

[Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘

[Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘

 

 

 

📌 선형 에라토스테네스의 체 (선형 체, Linear Sieve)

기존 에라토스테네스의 체는 소수를 구하는 가장 빠르고 효율적인 알고리즘으로 많이 알려져 있다.

시간 복잡도가 $O (N\;log\;log\;N)$ 으로 충분히 빠른 건 사실이다.

 

 

 

하지만, 이 알고리즘에 한 가지 아쉬운 점이 있다면, 이미 제거한 배수들이 또다시 탐색의 대상이 된다는 점이다.

 

예를 들어, 2의 배수들을 제거한 후 3의 배수를 제거하는 상황에서 6과 12 같은 경우는 2에서 이미 제거를 했음에도 불구하고, 3의 배수를 제거하는 과정에서 다시 제거를 위한 시도를 한다.

 

결국, 6과 12 같은 합성수는 중복된 연산을 거치게 된다.

 

 

중복된 연산을 보면 불편해!

 

이를 보완하여 더 효율적으로 소수를 찾는 알고리즘이 바로 선형 에라토스테네스의 체다.

일부에서는 "선형 에라토스테네스의 체 "이외에 "오일러의 체" 또는 "선형 체"라고 부르기도 한다.

 

소수의 배수를 제거하는 과정에서, 합성수(소수가 아닌 수)는 단 한 번, 가장 작은 소인수만을 사용하여 배수를 제거하는 게 핵심이다.

큰 소인수에 의해 다시 지워지지 않기 때문에 불필요한 중복 연산이 제거되어 더 빠른 속도로 소수를 구할 수 있다.

 

 

⏱ $\mathbf{O(N)}$ 의 시간 복잡도를 가진다.

 

 

 

 

 

📌 선형 에라토스테네스의 체: 동작 원리

2부터 n까지의 범위에서 소수를 찾아내는 방법은 아래와 같다.

 

❕ 초기화

• 크기 n의 배열 least_prime을 생성하여 각 숫자의 가장 작은 소인수를 기억해야 한다. (처음에 모두 0으로 초기화)

❕ 소수 구하는 과정

1. 2부터 n까지의 숫자를 나열한다.
2. 첫 숫자는 2이다. least_prime[2]는 0이므로 2를 소수로 선택하고, 2의 배수인 4, 6, 8 등의 숫자들을 제거한다.
   • 이때, least_prime[4], least_prime[6], least_prime[8] 등을 모두 2로 설정한다.
3. 다음으로 3을 만나면, least_prime[3]이 0이므로 3은 소수로 선택하고, 3의 배수인 6, 9, 12 등을 제거한다.
   • 이때, least_prime[6], least_prime[9], least_prime[12] 등을 모두 2로 설정한다.
   • least_prime[6]은 이미 2로 설정되어 있기 때문에 6은 더 이상 처리되지 않는다.
4. 다음으로 4를 만나면, least_prime[4]가 이미 2로 설정되어 있다. 따라서 4는 소수가 아니라고 판단하여, 소수로 선택하지 않는다.
5. 4의 배수를 처리할 때, 소수 리스트에 있는 소수들(현재 2와 3)에 대해서만 처리한다.
   • 2와 4의 곱인 8을 제거한다. 이때, least_prime[8] = 2 로 설정한다.
   • 3과 4의 곱인 12를 처리해야 하지만, 3은 4의 가장 작은 소인수인 2보다 크므로 더 이상 처리되지 않는다. (이미 위의 3번 과정에서 least_prime[12]가 2로 처리된 걸 이런 식으로 건너뛰게 된다!)
6. 위 과정을 n까지 반복한다.

 

🔎 n의 제곱근이 아닌 "n까지" 반복한다! 

 

기존 에라토스테네스의 체는 n의 제곱근까지 반복하면 모든 소수를 구할 수 있었지만, 선형 에라토스테네스의 체는 그럴 필요가 없다.

이 알고리즘의 핵심은 각 숫자를 한 번만 처리하면서 중복 없이 모든 배수를 효율적으로 제거하는 것이기 때문에, 제곱근에 한정된 반복이 아니라 전체 범위 2부터 n까지 전부 탐색해도 $mathbf{O(N)}$ 시간 복잡도를 유지할 수 있다!

 

 

 

 

 

📌 선형 에라토스테네스의 체: 코드 구현

선형 에라토스테네스의 체를 C++코드로 구현하면 아래와 같다.

#include <iostream>
#include <vector>
using namespace std;

void LinearSieve(int n) {
    vector<int> primes;   // n까지의 소수를 저장할 리스트 생성
    vector<int> least_prime(n + 1, 0);  // 각 숫자의 가장 작은 소인수를 기록하는 배열 생성

    /* 2부터 시작하여 n까지 반복 */
    for (int i = 2; i <= n; i++) {
        /* i가 소수인 경우 처리 */
        if (least_prime[i] == 0) {
            least_prime[i] = i;     // i는 자기 자신의 가장 작은 소인수
            primes.push_back(i);    // i를 소수 리스트에 추가
        }

        /* 소수의 배수를 제거 */
        for (int p : primes) {
            if (p > least_prime[i] || p * i > n) break; // 소인수가 작은 순서대로만 처리
            least_prime[p * i] = p; // p는 p * i (p의 배수)의 가장 작은 소인수
        }
    }

    /* 소수 출력 */
    cout << "2부터 n까지의 소수: ";
    for (int p : primes) {
        cout << p << ' ';
    }
}

int main() {
    int n;
    cout << "입력: ";
    cin >> n;

    LinearSieve(n);
}

 

입출력 결과

입력: 144
2부터 n까지의 소수: 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 101 103 107 109 113 127 131 137 139

 

 

 

 

 

---

참고

 

Linear Sieve - Algorithms for Competitive Programming

Linear Sieve - Algorithms for Competitive Programming

 

PS를 위한 수학 - Linear Sieve(오일러의 체)

PS를 위한 수학 - Linear Sieve(오일러의 체)

 

에라토스테네스의 체 - 위키백과

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전