[알고리즘] 백준 1153 파이썬 - 네 개의 소수

 

1153번: 네 개의 소수

문제

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

 

문제풀이

n=int(input())
#01
tmp=[False,False]+([True]*(n-1))
prime=[]
for i in range(2,n+1):
    if tmp[i]:
        prime.append(i)
        for j in range(2*i,n+1,i):
            tmp[j]=False
size=len(prime)

#02
ans=[]
def goldbach(num):
    for i in range(size):
        for j in range(size):
            sum=prime[i]+prime[j]
            if sum==num:
                ans.extend([prime[i],prime[j]])
                return
            elif sum>num:
                break
#03
if n<8:
    print(-1)
else:
	#04
    if n%2==0:
        ans=[2,2]
        n-=4
        goldbach(n)
        print(*ans)
    #05
    else:
        ans=[2,3]
        n-=5
        goldbach(n)
        print(*ans)

- #01 : 에라토스테네스의 체를 이용하여 prime에 n까지의 소수를 저장한다.

- #02 : 골드바흐의 추측을 이용하여 입력받은 num이 두 소수의 합으로 표현되면,

           ans에 두 소수를 extend한 후 return한다. 

           만약 sum이 num보다 더 크다면 break한 후 다음 for문을 돈다.

- #03 : n이 8보다 작으면 최소 값인 2+2+2+2로도 표현 불가하기에 -1을 출력한다.

- #04 : n이 짝수이면, 네 개 중에 2개는 [2,2]로 채우고 나머지 2개는 골드바흐의 추측을 사용한다.

           참고로 n과 n-4 모두 짝수이므로, 골드바흐의 추측을 사용하는데 문제가 되지 않는다.

           [2,2,prime[i],prime[j]]까지 총 4개의 값을 한 줄에 출력해준다.

- #05 : n이 홀수이면, 네 개 중에 2개는 [2,3]로 채우고 나머지 2개는 골드바흐의 추측을 사용한다.

           또한 n과 n-5 모두 홀수이므로, 골드바흐의 추측을 사용하는데 문제가 되지 않는다.

           [2,3,prime[i],prime[j]]까지 총 4개의 값을 한 줄에 출력해준다.