[백준/파이썬] 9020번 골드바흐의 추측 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 9020번 골드바흐의 추측
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

짝수 n을 두 소수의 합으로 나타낼 때 차이가 가장 작은 소수 쌍을 출력하는 문제입니다.

코드

from sys import stdin

def prime_list(n):
    sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i): 
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

pri = prime_list(50000)

def bin_search(x, dest, start, end):
    while True:
        index = (start + end) // 2
        if(x+pri[index] == dest):
            return index
        elif(start>=end):
            return -1
        elif(x+pri[index] < dest):
            start = index + 1
        else:
            end = index - 1

for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    ans = 0, 10000
    for i in range(len(pri)):
        if(i > (n/2)): break
        j = bin_search(pri[i], n, i, len(pri)-1)
        if(j == -1): continue
        if(ans[1]-ans[0] > pri[j]-pri[i]): ans = pri[i], pri[j]
        if(ans[0]==ans[1]): break

    print(" ".join(map(str, ans)))

설명

에라토스테네스로 소수 목록을 만든 뒤, 각 소수에 대해 이분 탐색으로 짝 소수를 찾아 최소 차이 쌍을 갱신합니다.

---

• 백준 문제풀이 전체 목록 보기

---