개발자 이민재입니다.

POSTS

에라토스테네스 체 구현 및 시간복잡도 분석

4min read

Overview

에라토스테네스의 체는 1부터 N까지 소수를 구하는 방법입니다. 소수를 구하는 과정은 다음과 같습니다.

이제부터 에라토스테네스의 체 알고리즘의 구현을 살펴보고, 시간복잡도가 O(Nlog⁡log⁡N) O(N \log\log N)인 이유를 알아보겠습니다.

에라토스테네스의 체 구현 코드(C++)

vector<int> Eratosthenes (int n) {
    vector<int> answer;
    bool arr[1000001] = {false};
    for(int i = 2; i * i <= n; i++) {
        if(!arr[i]) {
            for(int j = i*i; j <= n; j += i)
                arr[j] = true;
        }
    }

    for(int i = 2; i <= n; i++) {
        if(!arr[i]) answer.push_back(i);
    }
    return answer;
}

연산 횟수

구현 코드에서 NN에 대해 대략적인 연산 횟수를 세어보면 다음과 같습니다. 코드 상에서 최적화한 부분이 있긴 하지만, 크게 봤을 때 연산 횟수는 다르지 않습니다. (참고 - i*i가 int type의 최댓값보다 크면 overflow가 발생하므로 주의가 필요합니다.)

N2+N3+N5+⋯=N×∑p≤n1p\frac{N}{2}+\frac{N}{3}+\frac{N}{5}+\cdots = N \times \sum_{p \leq n} {\frac{1}{p}}

여기서 우변은 NN보다 작은 소수의 역수들의 합입니다.

시간복잡도 증명

에라토스테네스의 체의 시간복잡도가 Ω(log⁡log⁡N)\Omega(\log\log N) 임은 잘 알려진 증명을 통해 알 수 있습니다.
하지만 ∑p≤n1p\sum_{p \leq n} {\frac{1}{p}}이 O(log⁡log⁡N) O(\log\log N) 이라는 것은 알 수가 없어서 찾아봤더니 아래 링크의 질문글에 답변이 있었습니다. Big-O 증명

근데 위 답변글은 함축적으로 수식을 전개해서 이해하기가 힘들어서, 이를 단계적으로 풀어 나름대로 해석해보았습니다. 알려진 증명과 Big-O notation의 정의를 숙지해서 형식에 맞게 잘 끼워맞추는 것이 중요한 것 같습니다.

1단계 - 정수론의 기본 정리

먼저 식을 간단히 하기 위해, 다음과 같이 정의합니다.

A=∑p≤n1pA=\sum_{p \leq n} {\frac{1}{p}}

이 때, p1,p2,⋯ ,pk≤Np_{1},p_{2},\cdots,p_{k}\leq N 을 만족하는 자연수 kk에 대해 AkA^{k}를 다음과 같이 간단히 쓸 수 있습니다.

Ak=∑p1,p2,⋯ ,pk≤N1p1p2⋯pkA^{k}=\sum_{p_{1},p_{2},\cdots,p_{k}\leq N}{\frac{1}{p_{1}p_{2} \cdots p_{k}}}

여기서 1≤p1p2⋯pk≤Nk1 \leq p_{1}p_{2} \cdots p_{k}\leq N^{k} 이고, m=p1p2⋯pkm = p_{1}p_{2} \cdots p_{k}로 표현할 수 있는 자연수 mm은 p1,p2,⋯ ,pkp_{1}, p_{2}, \cdots, p_{k}가 모두 다를 경우 AkA^{k} 식에서 최대 k!k!번 나타납니다. 따라서, 다음이 성립합니다.

Ak=∑p1,p2,⋯ ,pk≤N1p1p2⋯pk≤k!∑i=1nk1iA^{k}=\sum_{p_{1},p_{2},\cdots,p_{k}\leq N}{\frac{1}{p_{1}p_{2}\cdots p_{k}}} \le k! \sum _{i=1}^{n^{k}}{\frac{1}{i}}

2단계 - 적분

이 부분은 적분 관계식에 의해 쉽게 알 수 있습니다. 즉,

ln⁡(nk+1)=∫1nkdxx=∑i=1nk∫ii+1dxx\ln(n^{k}+1)=\int_{1}^{n^{k}}{\frac{dx}{x}}=\sum_{i=1}^{n^{k}}{\int_{i}^{i+1}{\frac{dx}{x}}}

에서 다음이 성립합니다.

12∑i=1nk1i≤∑i=1nk∫ii+1dxx=ln⁡(nk+1)\frac{1}{2}\sum_{i=1}^{n^{k}}{\frac{1}{i}} \le \sum_{i=1}^{n^{k}}{\int_{i}^{i+1}{\frac{dx}{x}}} = \ln (n^{k}+1)

식을 마무리하면, 아래와 같습니다.

Ak=∑p1,p2,⋯ ,pk≤N1p1p2⋯pk≤k!∑i=1nk1i≤k!×2ln⁡(nk+1)A^{k}=\sum_{p_{1},p_{2},\cdots,p_{k}\leq N}{\frac{1}{p_{1}p_{2}\cdots p_{k}}} \le k! \sum _{i=1}^{n^{k}}{\frac{1}{i}} \le k! \times 2 \ln (n^{k}+1)

이제 kk 제곱근을 취하면, 아래와 같습니다. ((k!)1/k≤(kk)1/k≤k(k!)^{1/k} \le (k^{k})^{1/k} \le k 과, k1/k=e(ln⁡k)/k≤ek^{1/k}=e^{(\ln k) / k} \le e 이용)

A≤(k!2kln⁡n)1/k≤2ek(ln⁡n)1/kA \le (k!2k \ln n)^{1/k} \le 2ek(\ln n)^{1/k}

3단계 - Big-O 증명

이제 Big-O notation의 정의에 의해, 모든 n≥n∗0n \ge n*{0} 에 대해 0≤f(n)=2ek(log⁡n)1/k≤clog⁡log⁡n0 \le f(n)=2ek(\log n)^{1/k} \le c\log\log n인 양의 상수 c,n∗0c, n*{0}가 존재하는지만 판단하면 됩니다.

자연수 k=⌈ln⁡ln⁡n+1⌉k=\lceil \ln \ln n+1\rceil 로 정의하면 2ek(ln⁡n)1/k≤2e2(ln⁡ln⁡n+1)2ek(\ln n)^{1/k} \le 2e^{2}(\ln \ln n +1) 이므로, n≥3n \ge 3에 대해 c=2e2(ln⁡ln⁡3+1)/ln⁡ln⁡3c=2e^{2}(\ln \ln3+1)/\ln\ln 3 으로 두면 f(n)=O(ln⁡ln⁡n)f(n)=O(\ln\ln n) 이 증명됩니다.