[알고리즘/백준] 6588: 골드바흐의 추측(python)

일단 에라토스테네스의 체를 이용해서 소수를 다 구한다.

나는 array의 길이만큼 for문을 돌리되, i가 작은 수부터 시작되기 때문에
만약 array[i]와 array[n-i]가 둘다 array에 존재할 경우 해당 값을 출력하고 바로 break를 걸었다.

a = [False, False] + [True] * 1000000
for i in range(2, 1001):
    if a[i]:
        for j in range(2*i, 1000001, i):
            a[j] = False

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(3, len(a)):
        if a[i] and a[n-i]:
            print(f'{n} = {i} + {n-i}')
            break