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

최종 코드

최종 코드는 아래와 같다. 에라토스테네스의 체를 활용해야 하는 문제였다.

MAX = 1000000
# MAX = 1000

ansIndex = [1] * (MAX + 1) # 전체 index를 1(소수) 로 설정

for i in range(3, int(MAX ** 0.5) + 1, 2): # i를 3부터 시작하여 MAX의 제곱근까지, 홀수로 증가시키는 루프를 설정
    if ansIndex[i] == 1: # 현재 숫자 i가 소수인지 확인
        for j in range(i * 2, MAX, i):
            ansIndex[j] = 0

while True:
    k = int(input())
    if k == 0:
        break
    for i in range(3, int(k / 2) + 1, 2): # 소수 i의 배수를 찾기 위한 루프. 3부터 k/1 까지 2씩 증가시킨다.
        if ansIndex[i] and ansIndex[k - i] == 1: # i와 k-i의 값이 모두 1(소수) 이면
            print(f"{k} = {i} + {k - i}") # 출력
            break 
    else:
        print("Goldbach's conjecture is wrong.")

풀이

주석을 달았지만, 이를 다시 문장으로 설명해보겠다.

 

처음에 ansIndex[i]를 1로 설정한다. 전체를 소수로 가정하는 것이다.

또한, 이 루프가 소수 중에서 홀수만 다루기 때문에 2는 소수이지만 짝수이므로 별도로 처리하지 않고, 2를 소수로 가정한다.

i를 3부터 시작해서 MAX의 제곱근까지, 홀수로 증가시키는 루프를 설정한다. 여기서 int(MAX ** 0.5)는 MAX의 제곱근을 구한 후 정수로 변환한다. (에라토스테네스의 체 알고리즘을 구현하는 부분)

현재 숫자 i가 소수인지 확인한다.

소수 i의 배수를 찾기 위한 루프이다. j를 i의 배수로 초기화하고, MAX까지 i씩 증가시키면서, ansIndex 리스트에서 j를 0으로 변경한다. 이는 소수의 배수를 모두 0으로 만드는 과정이다. 

 

이해를 돕기 위해 MAX를 작은 수로 가정해보자. 10으로 해보겠다.

ansIndex = [1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1] 이다.

 

MAX = 10일때

i는 3~9까지 2씩 증가한다. (소수이자 홀수인 수 찾기)

if [i]가 1일때 (소수일때) -> 3이 소수일때

j가 i*2 ~ 10(MAX) 까지 i씩 증가한다. -> 6(3의 배수) ~ 10 까지 3씩 증가한다. 

j = 0 -> 즉, 6 9 가 0이 된다.

 

k = 8일때

for 3 ~ i/2까지 2씩 증가한다. -> 3 ~ 4(= 8/2)까지 2씩 증가

if [i]와 [8-i]가 모두 1이면 -> 3과 5(= 8-3)이 모두 1이면

출력한다. -> 위 ansIndex에서 둘 다 1이므로 출력한다.

 

트러블슈팅

처음에는 아래처럼 진행하였다.

# MAX = 1000000
MAX = 1000

ansIndex = [1] * (MAX + 1)

for i in range(3, MAX + 1, 2):
    if ansIndex[i] == 1:
        ansIndex[i] = 1

print(f"ansIndex = {ansIndex}")

while True:
    k = int(input())
    if k == 0:
        break
    for i in range(3, int(k / 2) + 1, 2):
        print(f"i = {i} k - i = {k - i} ansIndex[i] = {ansIndex[i]} ansIndex[k - i] = {ansIndex[k - i]}")
        if ansIndex[i] and ansIndex[k - i] == 1:
            print(f"{k} = {i} + {k - i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

그러나 찍어봤을때 

8
20
42
0
i = 3 k - i = 5 ansIndex[i] = 1 ansIndex[k - i] = 1
8 = 3 + 5
i = 3 k - i = 17 ansIndex[i] = 1 ansIndex[k - i] = 1
20 = 3 + 17
i = 3 k - i = 39 ansIndex[i] = 1 ansIndex[k - i] = 1
42 = 3 + 39

와 같이 42에서 잘못 된 값이 출력되었다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다 이 부분을 만족하지 않기 때문인데, 모든 n을 만들 수 있는 방법을 추가하도록 구현하지 못했다.