[BOJ, 백준] 1153 네 개의 소수 python

1이상 백만 이하의 어떤 수가 주어졌을 때, 해당하는 수를 4개의 소수의 합으로 나타내는 문제가 되겠다.

 

 

여기서 한가지 알아두면 좋은 것이 골드바흐의 추측이다.

 

https://ko.wikipedia.org/wiki/%EA%B3%A8%ED%8A%B8%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

골트바흐의 추측 - 위키백과, 우리 모두의 백과사전

 

여기에서 수치적인 분석에 의하면 10^18까지는 해당 추측이 성립한다고 한다 !

 

-> 백만정도는 이 수치 안에 포함되므로 어렵지 않다는 것을 알 수 있겠다.

 

즉, 케이스를 나눠본다면 다음과 같이 나눌 수 있겠다.

 

1. 주어진 수 N이 홀수 / 짝수 인가?

 

2-1. N이 홀수인 경우

짝수인 소수는 2 하나뿐이므로, 다음과 같이 케이스를 나눌 수 있겠다.

 

2-1-1. 4개의 숫자 중 2가 1개 존재하는 경우

그렇다면 N-2는 3이상의 세개의 소수의 합으로 나타내어지는가? 

계산의 편의를 위해, 이때는 세개 중 하나의 소수가 3이라고 해버리자.

그렇다면 N-5가 4이상인 짝수 일 때, 골드바흐의 추측을 인정한다면 나타낼 수 있다는 것이므로 소수의 집합을 반복문을 돌면서

N-5 = p1 + p2 (p1,p2는 소수)인지 확인해주면 되겠다.

 

2-1-2. 4개의 숫자 중 2가 3개 존재하는 경우

N-6이 소수인지 확인하면 되겠다.

 

2-2. 주어진 수가 짝수인 경우

마찬가지 짝수인 소수는 2만 존재하므로 다음과 같이 케이스를 나누자.

 

2-2-1. 4개의 숫자 중 2가 4개 존재하는 경우

이 경우에는 2,2,2,2로 나타내어진다는 것이므로, N이 8인지 체크

 

2-2-2. 4개의 숫자 중 2가 2개 존재하는 경우

2,2,p1,p2로 나타내어진다는 것이므로, N-4에 대해서 반복문을 순환해주면 되겠다. (2-1-1과 유사한 방법)

 

소스 코드는 다음과 같이 나온다.

 

import math
from collections import defaultdict
N = int(input())
def prime(n):

    num = [False for _ in range (0,n+1)]
    num[0] , num[1] = True, True
    m = int(math.sqrt(n) + 1)
    prime_number = []
    prime_num = defaultdict(int)
    for i in range (2, n+1):
        if num[i] == False and i != 2:
            prime_number.append(i)
            prime_num[i] += 1
            for j in range (i,n+1,i):
                num[j] = True
    #4이상의 짝수는 두 홀수인 소수의 합으로 나타낼 수 있다 -> Goldbach's conjecture

    #prime_number는 3이상의 소수들의 집합
    if n % 2 == 0:
        if n == 8:
            return [2,2,2,2]
        elif n - 4 >= 6: #3이상의 소수 2개의 합으로 이루어진 경우
            for x in prime_number:
                if prime_num[n-4-x] != 0:
                    return [2,2,x,n-4-x]

    elif n % 2 != 0:
        # 2가 3개 존재하고, 3이상의 소수가 1개 존재하는 경우
        if n - 6 in prime_number:
            return [2,2,2,n-6]
        else:
            #n-5를 2개의 소수의 합으로 나타내야하는 상황
            for x in prime_number:
                if prime_num[n-5-x] != 0:
                    return [2,3,x,n-5-x]
    return [-1]

print(*prime(N))