우주의 IT 소행성

MAX = 1000000
check = [0] * (MAX + 1)
check[0] = check[1] = True
prime = []

for i in range(2, MAX + 1):
    if not check[i]:
        prime.append(i)
        j = i + i
        while j <= MAX:
            check[j] = True
            j += i
prime = prime[1:]

while True:
    n = int(input())
    if n == 0:
        break
    for p in prime:
        if (n - p) < 0:
            print("Goldbach's conjecture is wrong.")
            break
        elif not check[n - p]:
            print(f'{n} = {p} + {n - p}')
            break

에라토스테네스의 체을 이용해 MAX인 1000000 까지의 소수의 배수들을 모두 걸러주고 PRIME 리스트를 만들어준다.

A + B = N ( A, B, C 는 모두 소수) 라는 골드바흐의 추측 공식을 기억해보자.

A가 P라고 할때 P + B = N 이고

B = N - P가 된다.

따라서 prime을 하나씩 꺼내주면서 n-p를 찾아주면 된다.

n - p가 음수일 경우 goldbach's conjecture is wrong을 출력해준다.

이전 포스팅 한 소수 구하기를 응용하여 풀 수 있다.

주어진 수를 소수의 작은 순서로 나누어 떨어지는 데 까지 나누고

마지막 남은 나머지가 소수 리스트 안에 있다면 해결

소수 리스트 안에 없다면 소인수 분해가 불가능 하다고 판단.

import math
n = int(input())
array = [True for i in range(n + 1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i]:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1


data = []
for i in range(2, n + 1):
    if array[i]:
        data.append(i)

while True:
    if n in data:
        print(n)
        break

    elif n == 1:
        break

    for i in range(2, n + 1):
        if n % i == 0:
            n //= i
            print(int(i))
            break