[백준] 1153번: 네 개의 소수 - [Python/파이썬]

 

문제

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

1153번: 네 개의 소수

임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다.

 

코드

def makeprime(n):
    a=[False, False] + [True]*(n)
    
    for i in range(2,n+1):
        if a[i]:
            for j in range(2*i, n+1, i):
                a[j]=False

    return a

n=int(input())
answer=''
if n<8:
    print(-1)
elif n%2==1:
    answer = "2 3 "
    n-=5
else:
    answer = "2 2 "
    n-=4

prime = makeprime(n)

for i in range(2, n+1):
    if prime[i] and prime[n-i]:
        answer+= str(i) + ' ' + str(n-i)
        print(answer)
        break

 

문제해결

 

골드바흐의 추측을 응용하는 풀이

9020번: 골드바흐의 추측

-> 모든 짝수는 소수의 두개의 합으로 표현 가능하다.

 

(1) N이 짝수일때 

 

N이 짝수일때는 N-4도 짝수이다. (N-4>=4)

따라서 N-4를 두개의 소수의 합으로 표현하고 (N-4=a+b), 4를 2+2로 표현하면

N=a+b+2+2로 표현할 수 있다.

 

(2) N이 홀수일때

 

N이 홀수일때는 N-5가 짝수가 된다. (N-5>=4)

따라서 N-5를 두개의 소수의 합으로 표현하고 (N-5=a+b), 5를 2+3으로 표현하면

N=a+b+2+3으로 표현할 수 있다.

 

이후 나머지 소수 a, b를 출력하는 함수를 만들어서 해결하였다.

​(기본적으로 에라토스테네스의 체를 활용하여 풀이하는것이 시간복잡도 측면에서 효율적이다)