[백준 Python] 6588번 골드바흐의 추측

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 

두 홀수 소수의 차가 가장 큰 소수로 출력해라

1. 짝수 정수 n 의 크기는 1.000.000 으로 작다.

2. arr[1000001] 배열로 1.000.000 까지의 수 중 홀수이며 소수인 것을 찾아 True 로 만들자 

3. arr[n=3] 부터 시작하여  arr[i] == arr[n-i] = True ( 홀수이며 소수인 수 ) 라면 출력한다.

# 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
# 소수 배열 구하기 (소수 = True, 아니면  = False )

arr = [True for i in range(1000001)]

for i in range(2,1001): # 소수가 아닌 놈 False 로 하기
    if arr[i]:
        for j in range(i + i, 1000001, i):
            arr[j] = False
            
while True:
    n = int(input())

    if n ==0:
        break
    
    for i in range(3,len(arr)):
        if arr[i] and arr[n-i]:
            print(n,"=",i,"+",n-i)
            break

★소수

1. 테스트케이스 마다 소수를 구할 수도 있지만 미리 배열에 소수를 구해놓을 수 있다.

2. 이때 각 숫자가 소수인지 판단하는 것이 아니라 "배수" 를 사용한다.

( arr[i] 가 소수라면 -> i 의 배수 arr 은 모두 소수 X )