[백준] 9020 - 골드바흐의 추측 [Python(파이썬)]

문제

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

풀이

소수와 관련된 문제는 앞서 풀어본 적이 있다.

이 문제는 주어진 짝수에 대해 골드바흐 파티션을 얼마나 빨리 구할 수 있는지가 관건이다.

 

골드바흐 파티션 함수는 두 개의 포인터로 구현할 수 있다.

각 포인터는 초기에 중간지점(mid)에 맞춰져있고, 소수를 가르킬 때까지 이동한다. 두 포인터가 소수를 가르키게 되면 검사를 하고 해당 소수의 합이 n인지 확인한다.

맞다면 골드바흐 파티션을 리턴하고, 아니라면 위 과정을 반복한다.

 

코드

import sys

def get_prime(MAX):
    for i in range(2, MAX+1):
        if isPrime[i]:
            for j in range(2*i, MAX+1, i):
                isPrime[j] = False

def get_goldbach_partition(n):
    l = r = n//2
    while True:
        while not isPrime[l]:
            l -= 1
        while not isPrime[r]:
            r += 1
        if l + r == n:
            return [l, r]
        elif l + r > n:
            l -= 1
        else:
            r += 1

MAX = 10000
t = int(sys.stdin.readline().strip())
isPrime = [False]*2 + [True for _ in range(MAX-1)]

get_prime(MAX)

for _ in range(t):
    n = int(sys.stdin.readline().strip())
    print(*get_goldbach_partition(n))