문제

문제는 이렇다.

백준 링크

정답 코드

# 소수이면 True인 전체 리스트 만들어두기.
sarr = [True for _ in range(1000001)]
for i in range(2, 1001):
    if sarr[i]:
        for j in range(i * 2, 1000001, i):
            sarr[j] = False

while True:
    n = int(input())
    if n == 0:
        break

    done = 0
    for i in range(3, len(sarr)):
        if sarr[i] and sarr[n-i]:
            print(f"{n} = {i} + {n-i}")
            done += 1
            break
    if done == 0:
        print("Goldbach's conjecture is wrong.")

풀이

에라토스테네스의 체를 사용은 하는데, 미리 소수리스트를 만들어놓는 것이 관건이었다.
그런데 그 소수 리스트가 소수만 들어있는 리스트가 아니라,
길이가 문제의 주어지는 인풋 숫자의 한계인 1000000인 리스트를 만들어서 인덱스가 소수인 부분의 원소는 False인 리스트를 만드는 것이었다.
이런 식의 생각은 못해봤는데, 익혀놔야겠다.

# 소수이면 True인 전체 리스트 만들어두기.
sarr = [True for _ in range(1000001)]
for i in range(2, 1001):
    if sarr[i]:
        for j in range(i * 2, 1000001, i):
            sarr[j] = False

우선 다 True인 길이 1000000짜리 리스트를 만들어놓고,
어떤 숫자의 배수는 다 False로 만드는 형식의 코드이다.
그렇게 되면
0) 리스트는 모든 값이 다 True로 시작, 1000000 = 1000 1000 이므로 1000까지만 검사하면 된다.
(상세설명) a b = 100이라고 했을 때, a = 1, b = 100 에서 시작해서 점점 중간으로 다가오다가 a와 b가 만나면 거기까지가 만들 수 있는 조합이 끝이기 때문이다. a가 보다 커져봤자, 그 a 값은 이미 b가 100에서 10까지 오는 길에 a와의 조합으로 만났던 숫자이기 때문.

1) 어떤 숫자가 True이면 일단 통과시켜서 그 수의 배수를 전부 False로 만들어놓음.
단, 그 숫자 자체는 처음 등장해서 True값을 가지고 있는 것이므로 해당숫자 2배수부터 False로 만든다.
2) 어떤 숫자가 False이면 이미 어떤 숫자의 배수라서 False가 된 것이므로 건너뜀.

• 또 하나 깨달은 점은, 그렇게 되면 인덱스가 0부터 시작하니까 불필요한 칸이 생긴다는 것에 너무 큰 신경을 쓸 필요가 없다는 것이다. 어차피 for문의 시작점을 필요한 숫자부터 시작할 것이기 때문에, 그냥 빈칸을 하나 만들어두고 그 빈칸은 안 쓰면서 코드를 짜는 게 더 효율적이다!