[백준] 6588 골드바흐의 추측 - 에라토스테네스의 체 (Python)

해당 문제에서는 제시된 수 보다 작은 소수들을 모두 알아야 한다. 그래서 얼마 전 소수 구하기를 풀면서 읽었던 책의 에라토스테네스의 체 알고리즘이 생각났다. 에라토스테네스의 체는 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스의 체 알고리즘은 다음과 같다.

 

1. 2 부터 N 까지의 모든 자연수를 나열한다.

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.

3. 남은 수 중에서 i 의 배수를 모두 제거한다. (i 는 제거하지 않는다)

4. 더 이상 반복할 수 없을 때까지 2 번과 3 번 과정을 반복한다.

 

나는 에라토스테네스의 체를... 어떻게 구현해야 할지 정말 모르겠어서 이번 딱 한 번만 이것 저것 구글링 해서 이해하고 코드를 작성해보기로 했다. 처음 보는 유형 대.깨를 할 수 없다 아직... 그 정도로도 아는 게 없기 때문 -> 변명이 진짜 아니당 감도 못 잡겠었다

# 소수 먼저 판별
import sys
input = sys.stdin.readline

r = 1000000

check = [True] * r

def main() :
    # 에라토스테네스의 체
    for i in range(2, int(r**0.5) + 1) : # i 번째 인덱스가 소수일 때
        if check[i] :
            for j in range(i*2, r, i) : # i 의 배수가 있을 때
                check[j] = False # 그 수는 false 

    while True : # 입력 받은 수가 에라토스테네스의 체에 속하는지?
        n = int(input().strip())
        
        if n == 0 :
            break
        else : # 두 소수의 합으로 표현될 수 있을까?
            for i in range(3,r) : # a 와 b 는 홀수이자 소수이므로 1 과 2 는 소수에서 제외한다.
                if check[i] :
                    if check[n-i] :
                        print("%d = %d + %d"%(n, i, n-i))
                        break

if __name__ == "__main__":
    main()