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

문제 설명

풀이 전략

n의 범위가 $2\leq n\leq 10000$ 이고 여러 번의 테스트 케이스를 적용하므로 $O(N^2)$의 시간 복잡도는 안된다. 소수 배열에서 조건을 만족하는 다른 소수를 찾으려면 in을 통하여 찾게 되는데, 이는 $O(N^2)$의 복잡도를 야기한다. 따라서 에라토스테네스의 체를 이용해 소수 배열을 구하지 않고 체 자체를 이용하여 인덱싱을 통하여 비교한 후 해결한다.

코드

k=10000
sieve=[False,False] + [True]*(k-1)
for i in range(2,int(k**0.5)+1):
    if sieve[i]:
        for j in range(2*i,len(sieve),i):
            sieve[j] = False

t = int(input())
for _ in range(t):
    n = int(input())
    for i in range(2,n//2 + 1):
        if sieve[i] and sieve[n-i]:
            result = i
    print(result,(n-result))