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

1. 문제

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

2. 접근 방법

예전에 했던 에라토스테네스의 체를 사용해서 풀었따.

 

시간 초과가 날 거 같아서

그냥 갯수만큼 리스트로 미리 소수를 구해놓고

 

a-b가 가장 큰 쌍을 구해야하니까, 결국 a가 가장 크고 b가 가장 큰 값이면 되니까

가장 작은 수부터 확인해서 a+b가 N이 될 때 둘 다 소수인지 확인하고 맞으면 바로 프린트하고 끄읕

3. 코드

python

wrong_msg = "Goldbach's conjecture is wrong."
prime = [False, False] + [True] * 1000000

for i in range(2, 1000000):
    if prime[i]:
        for j in range(2*i, 1000000, i):
            prime[j] = False

while True:
    N = int(input())
    a, b = 0, 0
    if N == 0:
        break
    for i in range(N):
        if prime[i] and prime[N-i]:
            a, b = i, N-i
            break
    if a * b != 0:
        print(f'{N} = {a} + {b}')
    else:
        print(wrong_msg)

4. 마치며

마치며~!