네 개의 소수

• 보통 네개의 수의 합을 갖고 푸는 문제들 (예를 들면 수집합) 에서 주로 쓰이는 테크닉은 두 수의 합으로 만들어질수 있는 숫자들을 모두 구해놓고, 그것을 이용해서 다시 네 수의 합에 대해서 조사하는 것이다.
• 그러나 이 문제는 그런 테크닉을 사용하기에도 범위가 너무 크다. 100만 이하의 소수의 갯수는 약 80000개인데, 그중에서 두개를 골라서 더해서 만들어지는 합의 갯수가 이미 감당 불가..
• 대신 골드바흐 추측을 이용하면 문제가 간단해진다. 이에 따르면 모든 짝수는 2개의 소수의 합으로 나눌수 있다. 이제 간단히, N에서 소수 2개를 빼서 짝수로 만든 다음에, 그 짝수를 2개의 소수의 합으로 나누기만 하면 된다. 처음에 빼줄 소수 2개는 N이 홀수면 2와 3을, N이 짝수면 2와 2로 처리하면 간단하다.
• 어떤 짝수 x를 2개의 소수의 합으로 나누는 것은 모든 소수 p에 대해서 x-p도 소수인지 확인하기만 하면 된다. 소수 목록을 구해서 set에 저장해두고 체크하면 된다. 소수 목록을 구하는 데에 O(nloglogn), 그렇게 얻은 O(n/logn)개의 소수에 대해서 x-p의 소수 여부를 체크하는 것은 O(1)이므로, 총 시간 복잡도는 O(nloglogn).

"""Solution code for "BOJ 1153. 네 개의 소수".

- Problem link: https://www.acmicpc.net/problem/1153
- Solution link: http://www.teferi.net/ps/problems/boj/1153

Tags: [Number theory]
"""

from teflib import numtheory


def main():
    N = int(input())

    if N < 8:
        print('-1')
        return

    if N % 2:
        answer = [2, 3]
        target = N - 5
    else:
        answer = [2, 2]
        target = N - 4
    primes = set(numtheory.prime_list(N))
    p = next(x for x in primes if target - x in primes)

    print(*sorted([*answer, p, target - p]))


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list