문제

[백준] 네 개의 소수 (Gold 3)

요약

임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하라. 불가능한 경우는 -1을 출력한다. 스페셜 저지이므로 여러 개의 답이 존재한다.

분류

  • 수학
  • 정수론
  • 에라토스테네스의 체
  • 소수 판정

풀이

내 풀이

골드바흐 추측을 알고 있었다면 수월하게 풀 수 있는 문제이다. 골드바흐는 “2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다”라고 하였다. 이는 ‘골드바흐의 강한 추측’이라 불린다.

  1. 입력된 자연수가 8 미만이라면 -1을 출력한다. 가장 작은 소수는 2이다. 따라서 8 미만의 자연수는 네 개의 소수의 합으로 분해할 수 없다.
  2. 입력된 자연수가 8 이상의 짝수라면, 2 + 2 + (짝수) 로 나타낼 수 있다. 여기서 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있기에, 두 소수 조합을 찾으면 된다.
  3. 입력된 자연수가 8 이상의 홀수라면, 2 + 3 + (짝수) 로 나타낼 수 있다. 역시 여기서 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있기에, 두 소수 조합을 찾으면 된다.

사실 골드바흐 추측은 후에 질문 게시글을 읽으며 알았고, 문제를 풀 때는 “2보다 큰 소수는 모두 홀수이니 대충 두 개 더하면 짝수 아닐까?” 라고 생각하고 풀었다. 수를 8부터 하나하나 쓰면서 생각했다.

import sys

n = int(input())
arr = []


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


if n < 8:
    print(-1)
    sys.exit(0)

if n % 2 == 1:
    n -= 5
    print("2 3 ", end="")
else:
    n -= 4
    print("2 2 ", end="")

for i in range(2, n + 1):
    if isPrime(i) and isPrime(n - i):
        print(i, n - i)
        break