python 백준 알고리즘 9020번: 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

일단 소수를 구하는 함수를 만들어놓고 두 소수의 차이가 가장 작은것을 출력해야하니 a, b를 각각 num // 2 으로 중간점부터 비교하는 식으로 구상해보았다.

 

내 제출

from math import sqrt

def prime(n):  # 소수 구하기 함수
    if n == 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

for _ in range(int(input())):  # test case만큼 반복문
    num = int(input())

    a, b = num//2, num//2  # 중간점부터 비교
    while a > 1:  # a를 -1 해나가니까 1보다 작아지면 안된다.
        if prime(a) and prime(b):
            print(a, b)
            break
        else:
            a -= 1
            b += 1

 

 

 

다른 방법이 있나 찾아보다가 정석적인 방법인것 같아 스크랩

n의 영역까지 소수 리스트를 만들어서 각 골드바흐 수를 딕셔너리 자료형으로 정리해 두 값의 차의 미니멈을 출력하는 방식

from math import sqrt

def prime(n):  # 소수 구하기
    if n == 1:
        return False
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

numbers = list(range(2,10001))  # 제한 영역까지
prime_list = set()

for i in numbers:
    if prime(i):
        prime_list.add(i)  # 소수 리스트 만들어놓기

t = int(input())  # test case

for k in range(t):
    k = int(input())
    dic = {}

    for i in prime_list:
        if k - i in prime_list:  # k에서 소수 i를 뺀값이 소수리스트에 있으면
            if i <= k - i:  # 첫번째 값이 입력받은 값보다 작거나 같을 때
                dic[(k - i) - i] = [i, k - i]  #  딕셔너리에 두값의 차를 키로하여 두 값 리스토로 저장

            else:
                dic[i - (k - i)] = [k - i, i]

    key_list = list(dic.keys())  # 두값의 차이들만 모아서 차이 리스트 생성
    print(dic[min(key_list)][0], dic[min(key_list)][1])  #두 소수의 차이가 가장 작은 것만 가져와서 하나씩 출력