[python] 9020. 골드바흐의 추측

• 문제

---

---

 

• 잘못된 풀이

import sys
T = int(input())

def check_prime(number):
    prime_ = [True] * number #number 갯수만큼 true list 만듦

    for i in range(2, int(number**0.5)+1): # 2부터 제곱근 n+1까지
        if prime_[i]: # i번째 index가 true이면
            for j in range(i*2, number, i): # 각 수의 배수
                prime_[j] = False

    return [i for i in range(2, number) if prime_[i] == True]

def find_min(result):
    min_list = []
    for i in range(len(result)):
        if result[i][0] <= result[i][1]: # 뒤에 숫자가 더 클 때
            value = result[i][1] - result[i][0]
            min_list.append(value)
        else:
            value = result[i][0] - result[i][1]
            min_list.append(value)
    idx = min_list.index(min(min_list))

    return result[idx][0], result[idx][1]


for i in range(T): # test case 개수
    n = int(sys.stdin.readline()) # 두 소수의 합 -> 소수의 차이가 가장 작은 것을 출력
    prime_list = []
    prime_list = check_prime(n) # 소수만 뽑았음

    result = []
    for j in prime_list: # 2, 3, 5, 7 ...
        if n-int(j) in prime_list:
            result.append((j, n-int(j))) # () 이렇게 들어감
    a, b = find_min(result)
    print(a, b)

 

코드가 이렇게나 길어지면 .. 잘못된 거 맞지 .... ㅎ ㅎ... 역시나 '시간초과'로 문제풀이를 실패하였다.

 

작성한 로직은 소수를 뽑는 check_prime과 차이가 가장 작은 값을 뽑는 find_min의 함수를 만들어

에라토스테네스의 체를 통해 문제를 해결하는 것이다. 하지만 실패 ....

 

개인적으로 생각한 실패 원인은, 가장 차이가 적은 두 소수를 합해서 해당 짝수가 되도록 하는 로직(find_min)이 길었기 때문인 것 같다.

 

 

• 올바른 풀이

def is_prime(n): # 소수 확인
    if n == 1:
        return False
    for j in range(2, int(n**0.5) + 1):
        if n % j == 0:
            return False
    return True


for _ in range(int(input())):
    num = int(input())

    a, b = num//2, num//2 # num을 반으로 쪼개고 a는 1을 빼고 b는 1을 더하면서 
    while a > 0:
        if is_prime(a) and is_prime(b): # 소수인지 확인
            print(a, b)
            break
        else:
            a -= 1
            b += 1

 

구글링을 하고 찾은 방법은 생각보다 많이 간단했다.

 

입력받은 num을 반으로 쪼개고 a, b를 만든다.

a가 0보다 크면 소수인지 판별하는 is_prime 함수를 통해, a와 b가 모두 소수인지 확인한다.

모두 소수이면 출력하는 방법이다.

 

내가 생각한 방법보다 훨씬 간단한 로직이었다... 나는 언제쯤 시간초과 없이 한번에 문제를 해결할 수 있을까 ....