백준 1153 <네 개의 소수> Python

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

---

합으로 구해야 하는 네 개의 소수 조합을 모두 찾는다면 시간초과가 발생합니다.

그렇다면 조합의 수를 줄여야 하는데, 여기서 사용할 수 있는 이론이 골드바흐의 추측입니다.

아직 증명되지는 않았지만 충분히 큰 수에 대해 모두 성립하는 추측이므로 해당 문제에서 사용할 수 있습니다.

 

모든 짝수에 대해 두 개의 소수의 합으로 표현할 수 있다는 것이 주된 내용인데, 그렇다면 N 이 주어졌을 때 미리 두개를 정해놓고 두개만 조합으로 구할 수 있습니다.

 

N 이 짝수인 경우, 골드바흐 추측을 사용하기 위해 N - K 도 짝수로 만들어야 합니다.

그렇다면 K 도 짝수이므로 합이 가장 작은 짝수의 조합인 [2, 2] 를 미리 정해놓을 수 있습니다.

N 이 홀수인 경우, 역시 N - K 는 짝수여야 하므로 합이 가장 작은 홀수의 조합인 [2, 3] 으로 미리 정해놓을 수 있습니다.

 

후에 N 에서 미리 정해진 값인 각각 4, 5 를 빼준 뒤 두 개의 소수 조합을 찾으면 됩니다.

---

import sys
from itertools import combinations_with_replacement
from math import sqrt

input = sys.stdin.readline


# N 이하의 소수 찾기
def find_unique(N):
    # 에라토스테네스의 체
    sieve = [1 for _ in range(N+1)]
    sieve[0] = 0
    sieve[1] = 0
    # 순회 범위
    root_N = int(sqrt(N))
    # 순회
    for num in range(2, root_N+1):
        # 체크되지 않은 수면
        if sieve[num]:
            for i in range(2*num, N+1, num):
                # 배수 모두 체크
                sieve[i] = 0
   
    # 체크되지 않은 수 리스트
    unqs = [i for i in range(len(sieve)) if sieve[i]]

    return unqs


def solution(N):
    # 골드바흐 추측에 의한 경우 분리
    # N 이 홀수면 N - K 가 짝수기 위해서는 K 는 홀수
    # -> 합이 가장 작은 홀수가 되는 소수 조합 = [2, 3]
    # N 이 짝수면 N - K 가 홀수기 위해서는 K 는 짝수
    # -> 합이 가장 작은 짝수가 되는 소수 조합 = [2, 2]
    # N 이 홀수면
    if N % 2:
        result = [2, 3]
        N -= 5
    # N 이 짝수면
    else:
        result = [2, 2]
        N -= 4
    # N 이하의 소수 리스트
    uniques = find_unique(N)
    # 조합
    for unqs in combinations_with_replacement(uniques, 2):
        # 조합의 합
        sum_unqs = sum(unqs)
        # 조합의 합이 N
        if sum_unqs == N:
            # 소수 리스트 최신화
            result.extend(unqs)
            return sorted(result)


# 입력
N = int(input().strip())
# N 이 8 미만이면 없음
if N < 8:
    print(-1)
else:
    result = solution(N)
    if result:
        print(*result)
    else: print(-1)