[백준/1153] 네 개의 소수 (Python)

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

1153번: 네 개의 소수

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:10:25

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

38

 

출력 예시

 

5 7 13 13

 

 

---

 

풀이

 

1. 1부터 N까지의 소수를 모두 알아내야만 하며, 이를 위해 에라토스테네스의 체 기법을 사용할 수 있겠다. 목표하는 최댓값 N의 약수는 최대 sqrt(N)까지 탐색함으로써 모두 알아낼 수 있으므로, [2, sqrt(N)] 범위 내에서 이 기법을 적용하도록 하자. 이 때 최종적인 시간복잡도는 O(NloglogN)이 된다.

 

2. 두번째로, 완전 탐색으로 합이 N임을 만족하는 네 소수를 구할 때이다. 우리는 에라스토테네스의 체로 어떤 수가 소수인지 아닌지 여부를 이미 전부 구한 바 있다. 따라서 O(p^3) (p는 prime number의 개수) 내에 모든 경우의 수를 따져 볼 수 있겠다 (소수인 수 i, j, k가 있다면, 남은 한 수 l = (N - i - j - k)가 소수인지 여부만을 판정해보면 된다)

 

 

풀이 코드

N = int(input())
M = int(N**0.5)
is_prime_num = [True for _ in range(N+1)]
is_prime_num[0] = is_prime_num[1] = False
for i in range(2, M+1) :
  if is_prime_num[i] :
    for j in range(i*2, N+1, i) : 
      is_prime_num[j] = False

prime_num = list()
for i in range(2, N+1) :
  if is_prime_num[i] :
    prime_num.append(i)

w = len(prime_num)
for i in range(w) :
  for j in range(i, w) :
    for k in range(j, w) :
      if prime_num[i] + prime_num[j] + prime_num[k] < N and is_prime_num[N - prime_num[i] - prime_num[j] - prime_num[k]] :
          print(prime_num[i], prime_num[j], prime_num[k], N - prime_num[i] - prime_num[j] - prime_num[k])
          exit()
print(-1)

풀이 완료!