[백준알고리즘] 6588번: 골드바흐의 추측 -Python

[백준알고리즘] 6588번: 골드바흐의 추측 -Python

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

6588번: 골드바흐의 추측

먼저 소수들을 구하기 위해서 에라토스테네스의 체를 사용했다. 에라토스테네스의 체를 통해 소수를 생성한 후에 하나의 소수 idx를 찾고, N-idx도 소수인지 확인하도록 했다. 이때 idx와 N-idx가 모두 소수일 때 두 수의 차가 최대가 되는 idx와 N-idx를 구해야 한다.

 

두 수의 차가 최대인 두 소수를 찾기 위해서 뒤에서부터 소수를 찾았다. 앞에서부터 찾게되면 소수의 간격이 작지만 뒤에서는 서로 다른 두 소수의 차가 매우 크고, 어차피 idx와 N-idx가 모두 소수이면서 차가 가장 크려면 idx가 가장 크고 N-idx는 가장 작아지기 때문이다.

 

아무튼 대부분이 같은 방식으로 푼 것을 확인했다. 그런데, 아직 4보다 큰 짝수가 소수들의 합으로 표현 안 되는 것이 없어서인지 통과한 코드에서 "Goldbach's conjecture is wrong."를 출력하지 않는 코드도 통과되어있는 것을 확인했다.

import sys

N = int(sys.stdin.readline())

prime = [1] * 1000001
prime[0], prime[1] = 0, 0
for idx in range(2, 1000001):
    if prime[idx]:
        jmp = 2
        while idx*jmp <= 1000000:
            prime[idx*jmp] = 0
            jmp += 1

while N:
    FIND = False
    for idx in range(N, N//2-1, -1):
        if prime[idx] and prime[N-idx]:
            sys.stdout.write("{} = {} + {}\n".format(N, N-idx, idx))
            FIND = True
            break
    if not FIND:
        sys.stdout.write("Goldbach's conjecture is wrong.\n")
    N = int(sys.stdin.readline())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다