[BOJ] 6588. 골드 바흐의 추측(Python)

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

# 33분 소요

 

• 에라토스테네스 체 이용해서 미리 소수 테이블을 만들어 놓는다. 참고(https://wikidocs.net/21638)
  • 이를 만드는 데 시간, 메모리 미리 소요해놓고 답을 구하는 데 걸리는 시간은 최소화한다.
• 가장 작은 소수인 2부터 두 수가 모두 소수인 가장 빠른 경우 정답 리턴

 

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

a = [0, 0] + [1]*(1000001-1)
for i in range(2, 1001):
    for j in range(2*i, 1000001+1, i):
        a[j] = 0

def solve(n):
    for num in range(2, n):
        if a[num] and a[n-num]:
            print(n, "=", num, "+", n-num)
            return
    print("Goldbach's conjecture is wrong.")
    return

while True:
    n = int(input())
    if not n:
        break
    solve(n)

---

• 고찰 : 어렵지 않은 문제인만큼 빠르게 푸는 힘을 갖자. 힘!