[BOJ] 9020번

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

Python3

if __name__ == '__main__':
    N = int(input())
    s = 10001
    prime = [True] * s
    prime[0] = False
    prime[1] = False
    for i in range(2, int(s**0.5)+1):
        if prime[i]:
            for j in range(i*2, s, i):
                prime[j] = False

    for _ in range(N):
        n = int(input())
        mid = n//2
        for i in range(mid, 1, -1):
            if prime[i] and prime[n-i]:
                print(i, n-i)
                break

테스트케이스를 여러번 받아 반복적으로 골드바흐 수를 구해야하는데 이때마다 소수를 구하기엔 시간 낭비로 느껴졌다. 따라서 N의 범위인 최대 10000까지의 수에 대해서 소수인지를 먼저 판별했다. 이때 알고리즘은 에라토스테네의 체를 통해 빠르게 구했다.

이후 문제를 보면 가능한 n의 골드바흐 파티션이 여러개일 경우 두 소수의 차이가 가장 작은 것을 출력하라고 되어있다. 짝수 중 예를 들어 10을 보면 5, 5가 골드바흐 수가 되는데 이 두 수는 10의 중간값이다. 즉 중간값을 기준으로 고를 때 가장 차이가 작은 골드바흐 수를 구할 수 있다. 따라서 입력받은 n의 중간 값 mid를 구하고 mid부터 1씩 빼가면서 소수를 찾았다. 만약 i 값이 소수일 때 n-i가 소수라면 이 두 수가 골드바흐 수가 되고 그때의 i와 n-i를 출력했다.