BOJ 1153 - 네 개의 소수 (Python3)

그간 정말로 격조했다. 메이플스토리에 빠져서 며칠 간 헤어나오지를 못했다...!

이번 문제는 간단한 수학 문제다. 소수 판정과 관련된 약간 심화된 문제. 그러나 난이도는 그렇게 어렵지 않다.

비슷한 유형의 문제를 몇 풀어 봤다면 코드 복붙으로 일정 구간은 날로 먹을 수 있으니 말이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

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

 

입력

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

 

예제 입력)

38

 

출력

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

 

예제 출력)

5 7 13 13

 

---

내 코드

prime = [True]*1000001
prime[0], prime[1] = False, False
for i in range(2, 1001):
    if prime[i]:
        for j in range(i*2, 1000001, i): prime[j] = False
n = int(input())
if n < 8: print(-1); quit()
else:
    l,u = [2,2+n%2],n-4-(n%2)
    if u == 4: l.append(2); l.append(2); l.sort(); print(*l)
    else:
        p = 3
        while True:
            if prime[p]:
                if prime[u-p]:
                    l.append(p); l.append(u-p);
                    l.sort(); print(*l); quit()
            p += 2

 

8 이상의 모든 자연수에 대해서는 네 개의 소수로 분해하는 방법이 반드시 존재한다. 만약 100만 이하에서 골드바흐 추측이 사실이라면 말이다.

8 이상의 짝수는 2 + 2 + (4 이상의 짝수)로, 9 이상의 홀수는 2 + 3 + (4 이상의 짝수)로 분해가 가능하고, 이 4 이상의 짝수는 두 소수의 합임이 골드바흐 추측에 의해서 보장되어 있다.

 

n이 7 이하라면 볼 것도 없다. -1을 출력하고 프로그램을 끝낸다.

먼저 1백만까지의 수들에 대해서 소수인지 판별하는 배열을 미리 생성해 둔다. 그 이후 출력할 소수들의 리스트 l을 생성.

n이 홀수라면 그 리스트에 [2, 3]을, 짝수라면 [2, 2]를 저장한다. 그리고 u에는 n-4 혹은 n-5를 저장. 이는 항상 4 이상의 짝수가 된다.

그 이후 u가 4라면 l에 2, 3를 추가하고, 6 이상이라면 3 이상의 홀수 p에 대해서 p, u-p가 동시에 소수가 되는 p를 찾은 뒤 l에 p, u-p를 추가시켜 준다.

마지막으로 정렬된 l을 출력하면 끝이다.

 

이로서 1153번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.