[백준][6588] 골드바흐의 추측

• 문제
  • 6588번: 골드바흐의 추측
• 해설

import sys

data = [int(x.strip()) for x in sys.stdin.readlines()][:-1]

def prime_candidate_generator_less_than(n):
    # 3, 5, 7, 11, 13, 17, 19, ...
    yield 2
    yield 3
    candidate = 5
    increment = 2
    increment_changer = {2: 4, 4: 2}
    while candidate <= n:
        yield candidate
        candidate += increment
        increment = increment_changer[increment]

def get_primes_by_sieve_less_than(n):  # n >= 6
    prime_list = []
    sieve_list = [True] * (n + 1)
    for candidate in prime_candidate_generator_less_than(n):
        if sieve_list[candidate]:
            prime_list.append(candidate)
            for i in range(2, 1 + (n // candidate)):
                sieve_list[candidate * i] = False
    return prime_list, sieve_list

prime_list, sieve_list = get_primes_by_sieve_less_than(max(data))
for i in data:
    for j in prime_list:
        if sieve_list[i - j]:
            print("{0} = {1} + {2}".format(i, j, i - j))
            break

• 포인트
  • 에라토스테네스의 체
  • 가장 큰 n에 대해서 체를 한번만 이용하기