[백준] 17103 - 골드바흐 파티션

🖥️ 시작하며

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

문제 조건에서 제한시간이 0.5초인 것을 봤을 때, 일반적인 방법으로 접근하면 시간 초과가 날 수 있는 문제다. 일일이 소수 판정 후 골드바흐의 추측을 판정할 시 시간이 오래 걸리므로, 에라토스테네스의 체를 이용하자.

💡 에라토스테네스의 체

에라토스테네스는 소수를 찾기 위해 소수를 찾는게 아닌 합성수를 제거하는 방식이다. 보통은 N을 입력받으면 2부터 N까지의 수 중 합성수를 제거하는 식으로 시작한다. 핵심 코드를 보자.


// 에라토스테네스의 체, N까지의 소수를 찾음
bool* Eratosthenes(int n) {
    bool* primes = (bool*)calloc(n + 1, sizeof(bool));
    for (int i = 2; i <= n; i++) {
        primes[i] = true;
    }
    
    for (int i = 2; i <= sqrt(n); i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes;
}


# 에라토스테네스의 체, N까지의 소수를 찾음
def Eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            primes[i * i :: i] = [False] * len(primes[i * i :: i])
    return primes

각각 C와 Python으로 구현한 에라토스테네스의 체다. 핵심 로직은 같다. 자세한 설명은 유튜브를 참고하는 것이 도움이 될 것 같다.

line by line으로 살펴보자.


primes = [True] * (n + 1)

N + 1 개의 bool 형 리스트를 생성한다. 우선 모두 소수라고 판정하기 위해 True로 세팅한다.


primes[0] = primes[1] = False

선제 조건으로 0과 1은 소수가 아니므로 거짓 처리한다.


for i in range(2, int(n**0.5) + 1):

2부터 N 의 제곱근 + 1까지 반복한다. 여기서 제곱근까지인 이유는, 어차피 제곱근의 수에서 N까지가 합성수로 판별되어 알아서 지워지기 때문이다.


if primes[i]:
		primes[i * i :: i] = [False] * len(primes[i * i :: i])

만약 primes[i] 가 True 라면, 즉 이전 단계에서 지워지지 않았고, 이는 즉 소수라는 말이니 해당 수의 배수들을 모두 False로 바꾼다. 예를 들어 i 가 2라면 2, 4, 6, 8 … 모두 지워진다.

그 아래 코드는 파이썬의 슬라이싱 기법을 이용한 코드인데, 약간 복잡하다. 결국에는 C의 코드와 같은 일을 한다. primes 배열의 i * i 부터 i 만큼 띄워진 부분들을 모두 False 로 만든다는 말이다.

이렇게 소수를 모두 구했다면 다음은 간단하다.

⚙️ 코드


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

// 에라토스테네스의 체, N까지의 소수를 찾음
bool* Eratosthenes(int n) {
    bool* primes = (bool*)calloc(n + 1, sizeof(bool));
    for (int i = 2; i <= n; i++) {
        primes[i] = true;
    }
    
    for (int i = 2; i <= sqrt(n); i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes;
}

int Solution(int n) {
    // 선제조건
    if (n <= 2 || n % 2 != 0) {
        return 0;
    }

    // 소수 구하기
    bool* primes = Eratosthenes(n);
    int count = 0; 

    // 소수끼리의 합이라면 정답처리
    for (int i = 2; i <= n / 2; i++) {
        if (primes[i] && primes[n - i]) {
            count++;
        }
    }

    free(primes); 
    return count;
}

int main() {
    int T, N;
    scanf("%d", &T);
    
    for (int i = 0; i < T; i++) {
        scanf("%d", &N);
        printf("%d\n", Solution(N));
    }

    return 0;
}


# 에라토스테네스의 체, N까지의 소수를 찾음
def Eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            primes[i * i :: i] = [False] * len(primes[i * i :: i])
    return primes


def Solution(n):
    # 선제조건
    if n <= 2 or n % 2 != 0:
        return 0

    # 소수 구하기
    primes = Eratosthenes(n)
    count = 0

    # 소수끼리의 합이라면 정답처리
    for i in range(2, n // 2 + 1):
        if primes[i] and primes[n - i]:
            count += 1

    return count


if __name__ == "__main__":
    import sys

    T = int(sys.stdin.readline())
    for i in range(T):
        N = int(sys.stdin.readline())
        print(Solution(N))

[백준] 17103 - 골드바흐 파티션

🖥️ 시작하며

💡 에라토스테네스의 체

⚙️ 코드

📌 소감

댓글