백준 (boj) 파이썬 - 6588번 : 골드바흐의 추측

문제 링크 : https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

---

 

에라토스테네스의 체 : https://infinitt.tistory.com/232?category=1105010

알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수)

 

 

 

 

처음에는 머릿속으로 구현하기 편하도록, 에라토스테네스의 체를 이용하여, 직접 소수가 들어있는 List를 구현했다.

이 List를 통해, if (입력받아온것 - List[0]) in List

와 같은 방식으로 검증을 했더니 당연히 시간초과가 발생했다. 사실 소수를 직접 list에 담지 않아도 상관없었고, 막상 구

현해보니  check에 들어있는 False True 값으로도 검증하는 과정도 어렵지 않았다.

 

 

 

파이썬 코드

r= 1000000

check = [True for _ in range(r)]

for i in range(2,int(r**0.6)):
    if check[i]==True:
        for j in range(i*2, r, i) : 
            if check[j] == True :
                check[j] = False            #에라토스테네스의 체


import sys
input = sys.stdin.readline


while(True):                               #입력받은 수가 에라토스테네스의 체에 속하는지, 즉 소수인지
    n = int(input())

    if n==0 : break
    for i in range(3,r):
        if check[i] == True:
            if check[n-i] == True :
                print("%d = %d + %d"%(n , i , n-i))
                break