BOJ 17103 골드바흐 파티션 (Linear Sieve - 다시..)

문제

짝수 $N$이 주어졌을 때, 두 소수의 합으로 나타내는 ‘골드바흐 파티션’의 개수 구하기

$N \le 1,000,000$, 시간 제한 0.5초.

여러 테스트 케이스가 주어지며, 파티션의 순서만 다른 경우는 같은 것으로 간주함 ($3+7$과 $7+3$은 1개).

복잡도 분석

전처리: $O(N \log \log N)$ (약 $10^6 \times 3.8 \approx 3.8 \times 10^6$ 연산)

쿼리당: $O(\pi(N))$ (최악의 경우 약 $7.8 \times 10^4$번 순회)

접근법

에라토스테네스의 체 활용해서 최대 범위까지 미리 소수 여부를 판별하는 전처리

그 뒤에는 소수 리스트를 만들고, 그것을 순회하도록 함

풀이

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 998244353; // or 1e9 + 7

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()

bool sieve[1000001];

void func(int N, vector<int> &prime){
    int res = 0;
    for(auto p: prime){
        if (p > N/2) break;
        if(sieve[N-p]){
            res ++;
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(sieve,sieve+1000001,true);
    sieve[0]=sieve[1]=false;

    for(int i=2;i*i<1000001;i++){
        if (sieve[i]){
            for(int j=i*i;j<1000001;j+=i){
                sieve[j]=false;
            }
        }
    }

    vector<int> prime;
    rep(i,0,1000001){
        if(sieve[i])
        prime.push_back(i);
    }

    int n;cin>>n;
    while (n--){
        int a; cin >> a;
        func(a, prime);
    }
    

    return 0;
}

Sieve of Eratosthenes

Outer loop : $\sqrt{n}$

이건 설명 생략

Inner loop : i^2 부터 시작하는 이유

이전에 작은 숫자들부터 순차적으로 배수를 지웠다. i의 배수를 지울때, i보다 작은 숫자들과의 곱은 이미 이전에 처리되었음

$i=5$인 상황

• $5 \times 2 = 10$: 소수 $2$의 배수를 지울 때 이미 지워짐.
• $5 \times 3 = 15$: 소수 $3$의 배수를 지울 때 이미 지워짐.
• $5 \times 4 = 20$: 소수 $2$의 배수를 지울 때 이미 지워짐.
• $5 \times 5 = 25$: 이전에 어떤 소수에 의해서도 지워지지 않은 첫 번째 배수

시간복잡도

에라토스테네스의 체 연산 횟수는 다음과 같은 급수의 합으로 표현

\[\sum_{p \le \sqrt{n}} \frac{n}{p} = n \left( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \dots + \frac{1}{p_{max}} \right)\]

소수의 역수의 합($\sum \frac{1}{p}$)은 메르텐스 제2정리(Mertens’ Second Theorem)에 의해 다음과 같이 근사

\(\sum_{p \le n} \frac{1}{p} \approx \ln(\ln n) + M\)따라서 전체 시간 복잡도는 다음과 같습니다.\(O(n \log (\log n))\)

선형 시간($O(n)$)에 매우 근접

Linear Sieve

일반적인 체의 문제는 중복 마킹입니다. 예를 들어 $30$은 $2$의 배수로 지워지고, $3$의 배수로 또 지워지며, $5$의 배수로 또 지워집니다.

모든 합성수를 ‘가장 작은 소인수(Smallest Prime Factor, SPF)’를 통해서 단 한 번만 지우도록 설계합니다. 이를 통해 $O(n)$의 시간 복잡도를 달성합니다.

const int MAX = 1000000;
int spf[MAX+1] =; // Smallest Prime Factor
vector<int> primes;

void linearSieve(){
    for(int i=2;i<=MAX;i++){
        if(spf[i]==0) { // 소수인 경우
            spf[i]=i; // 소수의 최소 소인수는 자신
            primes.push_back(i);
        }
        // 찾은 소수 리스트를 순회
        for (int p:primes){
            if(p>spf[i] || i*p > MAX) break; // 중복 방지
            // if (i%p==0 || i*p > MAX) break;
            spf[i*p] = p; // i*p 의 가장 작은 소인수는 p
        }
    }
}

모든 숫자를 정확히 한번만 방문하도록 함

소인수분해

vector<int> getFactorization(int x) {
    vector<int> factors;
    while (x > 1) {
        factors.push_back(spf[x]); // 가장 작은 소인수 추가
        x /= spf[x];               // 해당 소인수로 나누어 업데이트
    }
    return factors;
}

• 숫자의 범위: $X$가 우리가 미리 만든 spf 배열의 크기(MAX) 안에 있어야 합니다. (보통 $10^6$ ~ $10^7$)
• 질의 횟수: 소인수분해를 한두 번만 하고 말 거라면 $O(MAX)$의 전처리 비용이 아깝지만, 수백~수만 번 수행해야 한다면 무조건 이 방식입니다.