[백준] 9020. 골드바흐의 추측

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 하며, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

아래와 같이 에라토스테네스의 체를 이용해서 범위에 해당하는 소수들을 찾은 다음 복원추출하는 조합을 하면 쉽게 풀어낼 수 있는데, BOJ에 제출하면 시간초과가 뜬다.

from itertools import combinations_with_replacement


def prime(n):
    d = [i for i in range(2, n + 1)]
    c = {j for i in range(2, int(n ** 0.5) + 1) for j in range(i * 2, n + i, i)}
    return [v for v in d if v not in c]


for _ in range(int(input())):
    n = int(input())
    l = list(combinations_with_replacement(prime(n), 2))
    for x in [l[i] for i, x in enumerate(l) if sum(x) == n][-1]:
        print(x, sep=' ')

아래와 같이 절반인 수 부터 소수인지 확인하면서 확인 대상을 바꾸는 방법을 사용하면 통과가 가능해진다.

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


for _ in range(int(input())):
    n = int(input())
    a = b = n // 2
    while a > 0:
        if is_prime(a) and is_prime(b):
            print(a, b)
            break
        a -= 1
        b += 1

아래와 같이 에라토스테네스의 체를 사용해서 풀어내는 방법도 있는데, 오히려 연산 속도가 훨씬 느렸다. 아무래도 에라토스테네스의 체 함수를 개선할 필요가 있는 것 같다.

def prime(n):
    d = [i for i in range(2, n + 1)]
    c = {j for i in range(2, int(n ** 0.5) + 1) for j in range(i * 2, n + i, i)}
    return [v for v in d if v not in c]


for i in range(int(input())):
    n = int(input())
    l = prime(n)
    a = n // 2
    while a > 0:
        if a in l and n - a in l:
            print(a, n - a)
            break
        a -= 1

[백준] 9020. 골드바흐의 추측

Reference¶