greentea31's Note

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

풀이 과정

100만 이하의 모든 짝수 입력에 대해 두 홀수 소수의 합으로 나타낼 수 있는지 확인하면 된다.

100만 이하의 모든 소수를 에라토스테네스의 체로 구해서 배열에 넣어주고, 입력 받은 수 - 소수배열[i] (1 <= i < 소수배열 길이) 값이 소수면 두 홀수 소수의 합으로 나타낼 수 있는 것이니 출력해주면 된다.

코드

import sys

prime = []
primeCheck = [0] * 1000001

for i in range(2, 1000001):
    if primeCheck[i] == 0:
        prime.append(i)
        for j in range(2*i, 1000001, i):
            primeCheck[j] = 1

while True:
    n = int(sys.stdin.readline())
    if n == 0: break
    for i in range(1, len(prime)):
        if primeCheck[n - prime[i]] == 0:
            print(f'{n} = {prime[i]} + {n - prime[i]}')
            break