[백준] 9020번 : 골드바흐의 추측 - python

링크 : https://www.acmicpc.net/problem/9020

 

---

• 문제

 

 

 

---

• 설계하기(접근방법) 

1. 테스트 케이스 수를 입력받는다

2. 짝수 n을 입력받는다

 

방법 1.

n = 2k 를 2로 나눈다. k

순서쌍 (k + i, k - i)를 소수인지 아닌지 검사하며 i를 1씩 증가시킨다.

소수 순서쌍이 발견되면 반복문을 종료하고 순서쌍을 출력한다.

 

방법 2.

1 ~ 10000까지의 소수 리스트(primenum_list)를 만든다.

n = 2k를 2로 나눈 값 k와 가장 유사한 소수값을 찾고, 리스트의 위치(primenum_list[j])도 찾는다. ex) 근사한 소수 = k + i

k + i를 구했으면 k-i가 소수인지 확인한다

소수라면 출력, 아니라면 primenum_list에서의 인덱스 값을 1씩 줄여가며 반복한다.

---

• 코드(출력)

import sys

input = sys.stdin.readline

def find_primenumber(num):  # 소수 찾는 메서드
    if (num == 1):
        return 0
    for i in range(2, int(num ** 0.5)+ 1):
        if (num % i == 0):
            return 0
    return num


def find_nearnum(num, list):  # 리스트 내 가장 근사한 값을 찾는 메서드
    while (True):
        for i in list:
            if (i == num):
                return num
        num -= 1


primenumber_list = []

for i in range(1, 10001):  # 1 ~~ 10000까지 소수 리스트 구하기
    if (find_primenumber(i) > 0):
        primenumber_list.append(i)

t = int(input())

for i in range(t):
    num = int(input())  # num 입력받기
    p1 = int(num / 2)  # num 2로 나누기
    # 2로 나눈 값 primenumber_list에서 근사소수값 찾기
    middle_primenum_1 = find_nearnum(p1, primenumber_list)
    location = primenumber_list.index(middle_primenum_1)  # 근사소수값의 인덱스 위치 반환
    while (True):
        middle_primenum_2 = num - middle_primenum_1  
        if find_primenumber(middle_primenum_2) > 0: # 순서쌍이 소수인지 아닌지 검사
            print(middle_primenum_1, middle_primenum_2)
            break
        else:
            location -= 1  # 인덱스 값 1 감소
            middle_primenum_1 = primenumber_list[location]  # 세로운 중앙 소수값 대입

---

• 얻어갈 부분

1. 여러 시도를 하며 시간을 순차적으로 줄여나갔다. import sys를 이용하여 편리하게 줄일 수도 있지만, 그것은 마지막에 사용하자. 어떻게 하면 시간을 줄이면서 동시에 가독성 좋은 코드를 만들 수 있을지 고민해보자.