(백준, 파이썬) 9020 - 골드바흐흑님의 추측

파티션 기열! 악!!!

---

골드바흐의 추측

(https://www.acmicpc.net/problem/9020)

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다.

예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

 

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다.

10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오.

만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다.

출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한

4 ≤ n ≤ 10,000

---

-맞힌 코드-

#2보다 큰 모든 짝수(n)는 두 소수의 합으로 나타낼 수 있다
#10000 이하의 모든 짝수에 대해 골드바흐 파티션은 존재한다.
#두 소수의 차이가 가장 작은 파티션을 우선으로 출력
 
lst = [True] * (10000+1)   #소수 = True 깔고가기, +1은 0의 존재 때문에.
lst[0] = False
lst[1] = False
 
for i in range(2, int(len(lst)**0.5)+1):    #2부터 10000의 제곱근까지만 판별한다.
#ex) 64까지라고 치면, 8x8에서 64까지 모두 정리되기 때문.
    
    if lst[i] == True:  #만약 소수라면,
        for j in range(i+i, len(lst), i):   #그 소수의 2배수부터 lst의 끝까지, 모든 배수(+i)는
            lst[j] = False  #소수가 아니다. / 이게 가능한 건 초기 2와 3이 소수이기 때문.
 
lst_sosu = []   #위의 리스트는 bool형이기 때문에, 숫자로 넣어줄 소수 리스트를 따로 판다.
 
for i in range(len(lst)):
    if lst[i] == True:
        lst_sosu.append(i)  #소수면 그 녀석을 sosu_lst에 집어넣어 준다.
 
T = int(input())
 
for i in range(T):
    jjak = int(input())
 
#짝수를 어떻게 두 소수의 합으로 나타낼 것인가?
#입력받은 짝수를 반으로 쪼갠다.
#반이 소수라면, 그 소수 두 개를 파티션으로 한다.
    if (jjak/2) in lst_sosu:
        print(int(jjak/2), int(jjak/2))  
    
#아니라면, 그 짝수의 절반과 가장 가까운 소수를 기준으로 찾는다.
    else:
        for num in lst_sosu:
            if num > jjak/2:    #짝수의 절반보다 크다면(리스트가 오름차순이라 넘어가는 순간 걸리는 수)
                that = num  #그 수(that)가 우리가 찾는 수다.
                while jjak - that not in lst_sosu: #만약 jjak-that이 소수가 아니라면 (jjak-that, that 꼴로 파티션을 나타낼 수 없다면)
                    that = lst_sosu[lst_sosu.index(that)+1] #that은 그 다음 소수가 된다.
                print(jjak-that, that)  #while문이 끝났다면 출력한다.
                break 
            else:
                pass

어제 썼던 에라토스테네스의 체 원리를 이용했다.

어차피 10000까지여서, 새로 소수 리스트를 파줬고

메인은 차이가 가장 적은 두 소수의 합으로 파티션을 구현하는 것이었다.

 

오랜만에 맞히면서 짜릿했다.

---

 

 

9번 테마의 2번째까지 총 70개 풀었어.

앞으로 315개의 문제가 남았어. (18.2%)