[백준] 9020번 : 골드바흐의 추측 in 파이썬 쉽게 풀어보기

백준 9020 골드바흐의 추측 in python

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

---

코드

# n이하의 숫자들 중 소수 찾기
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]
 
# n이하의 소수들 중 합이 n
def sosu(n):
    li=prime_list(n)
    idx = max([i for i in range(len(li)) if li[i]<=n/2])
    for i in range(idx,-1,-1):
        for j in range(i,len(li)):
            if li[i]+li[j]==n:
                return [li[i],li[j]]
 
for _ in range(int(input())):
    n=int(input())
    print(" ".join(map(str,sosu(n))))

---

코드설명

1. prime_list function

>> 에라토스테네스의 체로 소수찾기 바로가기

2. sosu function

n이하의 소수들 중 합이 n이어야 하며 그 차이가 가장 작은 것을 return해야 한다.

따라서 찾은 소수들 중 max(n/2보다 작은 수) 부터 합이 n이 되는 수를 찾는다.

예를 들어 n=100일 때 li의 결과는

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 이다.

이 때, 50(=100/2)보다 작은 수 중 가장 큰 수인 47부터 합을 찾지 않고 2부터 합을 찾으면 그 결과는 3과 97이 된다.