Baekjoon 9020 - 골드바흐의 추측 (Python)

Baekjoon 9020 - 골드바흐의 추측

---

◎ Problem Definition

 

9020번: 골드바흐의 추측

---

◎ Implementation

1. Problem Type 

 - Implementation, math (Silver 1)

   #에라토스테네스의 체

2. Problem Analysis

▶ 용어 정의 : 골드바흐 파티션  

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있으며, 짝수를 두 소수의 합으로 나타내는 표현하는 것을 골드바흐 파티션이라고 한다. (10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.)

▶ 문제 풀이 : 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

3. Solution_1 (☆초기 접근)

▶ 완성 코드 

에라토스테네스의 체를 이용하여 소수 판단 list(prime_list)를 생성했습니다. prime_list의 값이 1이면 해당 index의 값은 소수입니다. 예를 들어, prime_list [3] = 1 이면, 3은 소수입니다. 

골드바흐 파티션의 두 수의 차가 가장 작은 것을 출력해야하기 때문에, 입력된 값(n)을 먼저 2로 나누어 중앙값 x를 찾고, x를 하나씩 증가시키면서 소수 여부를 확인합니다.

x와 n-x 값이 모두 소수이면 출력을 하게 됩니다.  

m = 10000
prime_list = [0, 0]+[1]*(m-1)
for i in range(2, int(m**0.5)+1):
    for j in range(i+i, m+1, i):
        if prime_list[j]:
            prime_list[j] = 0

for _ in range(int(input())):
    n = int(input())
    x = n//2
    while prime_list[x] == 0 or prime_list[n-x] == 0:
        x += 1
    print(n-x, x)

▶ 성능 

• Memory : 30864 KB
• Time : 508 msec

---

◎ Results

- 에라토스테네스의 체를 사용하여 소수를 구하고 최소의 차를 보이는 골드바흐 파티션을 구하는 재미있는 문제였습니다. 풀이는 했지만, 여전히 수행 시간 500msec 이상은 너무 많습니다. 어디서 줄일 수 있는지 더 고민이 필요합니다.