[Baekjoon] 17103/골드바흐 파티션/Python/파이썬/수학/에라토스테네스의 체

井·2025년 1월 15일

python 백준 소수판정 수학 알고리즘 에라토스테네스의체 정수론 파이썬

문제풀이

목록 보기

18/56

💡문제

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

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

예제입력

예제출력

📖내가 작성한 Code

import sys

MAX_NUM = 1000000


def sieve_of_eratosthenes():
    decimal_list = [True] * (MAX_NUM + 1)
    decimal_list[0], decimal_list[1] = False, False

    for num1 in range(2, int(MAX_NUM ** 0.5) + 1):
        if decimal_list[num1]:
            for num2 in range(num1 * num1, MAX_NUM + 1, num1):
                decimal_list[num2] = False
    return decimal_list


def find_goldbach_number(number, decimal_list):
    goldbach_numbers = 0
    for num in range(2, number//2 + 1):
        if decimal_list[num] and decimal_list[number - num]:
            goldbach_numbers += 1

    return goldbach_numbers


def main():
    speed_input = sys.stdin.readline
    N = int(speed_input())
    decimal_list = sieve_of_eratosthenes()
    for num in range(N):
        print(find_goldbach_number(int(speed_input()), decimal_list))


if __name__ == '__main__':
    main()

✍️풀이과정

저번에 풀었던 골드바흐의 추측과 거의 같은 코드 참고 바람
6588 골드바흐의 추측

🧠 코드 리뷰

추가 개선

미리 골드바흐 파티션 수 테이블(Precomputation)
2부터 1,000,000까지 전부 골드바흐 파티션 개수를 구해 goldbach_count[n]에 저장해놓으면, 테스트 케이스마다 O(1)로 처리가 가능.

🛠️AI 개선 코드

import sys

MAX_N = 1000000

def sieve_of_eratosthenes(n):
    """0 ~ n까지의 소수 여부를 담은 리스트를 반환합니다."""
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    return is_prime

def precompute_goldbach_counts(is_prime):
    """
    짝수 e(4 <= e <= MAX_N)에 대하여,
    골드바흐 파티션(두 소수의 합으로 e를 표현하는 방법)의 개수를
    미리 goldbach_count[e]에 저장합니다.
    """

    # 1. 소수 목록을 만든 뒤,
    primes = [i for i in range(2, MAX_N + 1) if is_prime[i]]

    # 2. 골드바흐 파티션 개수를 저장할 배열
    goldbach_count = [0] * (MAX_N + 1)

    # 3. 두 소수 p, q(p <= q)의 합이 e일 때,
    #    goldbach_count[e] += 1
    #    단, e가 MAX_N을 넘으면 더 이상 진행하지 않음(break).
    length = len(primes)
    for i in range(length):
        p = primes[i]
        for j in range(i, length):
            q = primes[j]
            s = p + q
            if s > MAX_N:
                break
            goldbach_count[s] += 1

    return goldbach_count

def main():
    input = sys.stdin.readline

    # 1) 에라토스테네스의 체로 소수 여부 리스트 구하기
    is_prime = sieve_of_eratosthenes(MAX_N)

    # 2) 짝수에 대한 골드바흐 파티션 개수를 미리 전처리
    goldbach_count = precompute_goldbach_counts(is_prime)

    # 3) 테스트 케이스 수 입력
    T = int(input())
    for _ in range(T):
        n = int(input())
        # n이 짝수일 경우 goldbach_count[n]을 출력
        # 문제 사양상 n은 짝수로 주어짐
        print(goldbach_count[n])

if __name__ == "__main__":
    main()