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

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

9020번: 골드바흐의 추측

2 이상의 짝수는 2개의 소수를 더한 값과 같다는 내용입니다.

그렇다면 어떤 소수의 합으로 표현이 가능한가? 만약에 여러 경우가 존재한다면 그중에서 소수끼리의 차이가 가장 적은 것으로 출력하시오.

접근 단계

• n까지의 소수를 구한다
• 가능한 소수 합의 조합을 구한다.
• 여러개라면 이 중에서 차이가 가장 적은 것을 출력한다.

시간 초과 난 소스 코드

from itertools import combinations_with_replacement
 
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+1, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]
 
def gold(primes,n):
    temp = list(combinations_with_replacement(primes,2))
    a = []
    for i in temp:
        if (i[0] + i[1]) == n:
            a.append(i)
 
    a.sort(key=lambda x:abs(x[0]-x[1]))
    return a[0]
 
T = int(input())
for i in range(T):
    n = int(input())
    primes = prime_list(n)
    answer = gold(primes,n)
    print(answer[0],answer[1])

에라토스테네스의 체로 소수를 구합니다.

이후 골드바흐처럼 합이 n값과 같은 것을 구하려고 했습니다.

시간 초과가 나더라구요.

계속 붙잡아도 몰라서 다른 분들의 풀이를 찾아봤습니다.

 

가장 차이가 적은 부분에 집중해서 푸시더라구요.

저처럼 조합이 아니라? 

https://deokkk9.tistory.com/20

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

이 분의 코드를 참고했습니다.

gold 함수 부분이 바뀌는데 저는 모든 리스트의 조합을 다 계산했습니다.

입력 받은 값 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 sieve
 
def gold(primes,n):
    index = 0
    while True:
        if primes[n//2-index] and primes[n//2+index]:
            return(n//2-index,n//2+index)
        index+=1
 
primes = prime_list(10001)
for _ in range(int(input())):
    n = int(input())
    answer = gold(primes,n)
    print(answer[0],answer[1])