[math3/Python] 9020번: 골드바흐의 추측 - 효과는 굉장했다!

9020번: 골드바흐의 추측

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

 

SOLUTION

import sys

sosu = [0 for i in range(10001)]
sosu[1] = 1 # 0 = 소수, 1 = 소수가 아닌 수
for i in range(2,101): # 제곱근까지만 탐색하면 되므로 10001 의 제곱근인 100 까지
    for j in range(i+i, 10001, i): # i의 배수들은 전부 소수가 아니므로 제외시킴
        sosu[j] = 1                # i + i 인 이유? 첫번쨰 i는 소수가 될 수 있기 때문에

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    
    half_n = n // 2 
    for j in range(half_n, 1, -1):
        if sosu[n-j] == 0 and sosu[j] == 0: # n의 절반에서 부터 탐색시작 두 소수의 차이가 가장 적게 만들기 위해
            print(j, n-j)
            break