6588 골드바흐의 추측 _python

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

6588번: 골드바흐의 추측

 

골드바흐의 추측

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

문제 그대로의 뜻인데, 어려운 문제는 아니다.

 

 

문제 접근

우선 소수를 활용해야 되는 문제인데, 입력을 받을 때 마다 소수를 확인한다면 시간초과가 날것이다.

1,000,000을 100,000번 입력받으면 연산이 너무 많아질 것이다.

그러면 소수를 미리 확인을 해두고 접근하는 방식을 써야하는데, 소수를 확인하기 위해선 에라토스테네스의 체를 활용하면 된다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위키에 있는 gif를 가져왔다.

소수의 모든 배수를 제거해나가는 방식.

2의 배수를 모두제거 -> 3의 배수를 모두 제거 -> 5의 배수를 모두제거 ...

범위까지 반복하면 된다.

 

이러면 소수만 확인가능한 배열이 있을 것이고,

이 배열의 i번째 소수만 참고해서 i와 N-i가 소수이면서, i와 N-i의 합이 N이 되는 경우를 찾으면 된다.

 

코드

import sys
input = sys.stdin.readline

#소수 골라내기 (에라토스테네스의 체 활용)
primeNum = [False, False] + [True]*999999

for i in range(2, 1000001):
    if primeNum[i]:
        for j in range(i*2, 1000001, i):
            primeNum[j] = False

#문제 풀이
while True:
    N = int(input())
    if N==0: break
    
    for i in range(N):
        if primeNum[i] and primeNum[N-i]:
            print("{0} = {1} + {2}".format(N, i, N-i))
            break