백준 #6588 골드바흐의 추측

마지막 수학 문제였다! 이거 다음엔 브루트 포스 부분으로 들어간다.

---

백준 #6588 골드바흐의 추측

문제

골드바흐의 추측을 검증하는 프로그램 작성
(조건: 백만 이하의 모든 짝수)

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

입력

• 한 개 이상의 입력
• 각 테스트 케이스는 짝수 정수 n 한개 (6 이상 100만 이하)
• 마지막에 0 입력 -> 이를 통해 입력 종료

제출 답

import math, sys

max = 1000000
# max = 100
array = [True for i in range(max+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
hasGold = False
input = sys.stdin.readline

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(max))+1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i*j <= max:
            array[i*j] = False
            j += 1


while True:

    hasGold = False
    inp = int(input().rstrip())

    if inp < 6 or inp > max or inp == 0:
        break

    for i in range(3, max+1, 2):
        if array[i] and array[inp - i]:
            hasGold = True
            print(inp, "=", i, "+", inp-i)
            break

    if not hasGold:
        print("Goldbach's conjecture is wrong.")
        break

---

일단 이 친구는 여러 개를 입력받는다는 점에서 소수를 하나씩 계속 비교할 수 없었다.
따라서 에라토스테네스의 체 알고리즘을 이용하여 소수를 판별할 수 있는 리스트를 만들었다.

만든 후 이를 계속 반복하여 i값이 소수일 때, n-i 또한 소수이면 되기 때문에 이를 찾아 출력하는 방식으로 진행했다.

이 문제는 시간 초과에 많이 걸려서 신경쓰던 문제였다.

그냥 소수 조건 구해서 하나하나 비교하자니 시간이 너무 걸렸고,
그래서 찾다가 다행히도 에라토스테네스의 체를 찾을 수 있어 이용했다.

그런데 또 시간 초과가 일어나서 어디를 줄일 수 있을까 했을 때, sys.stdin.readline 함수를 찾을 수 있어서 이걸 이용했더니 시간이 조금 더 줄어든 것 같다. 이때 다행히도 채점을 돌렸을 때 맞아서 이 잔인한 시간 초과의 늪에서 살아나올 수 있었다.

---

아쉬웠던 점

1. 에라토스테네스의 체 알고리즘의 경우 구글링을 통해 코드를 거의 데려온 것에 지나지 않았다.
   이에 대한 개념은 이해해서 다행이지만 다음에 사용할 때에는 내가 스스로 짤 수 있도록 해야 할 것 같다.
2. 소수를 구할 때에도 다양한 방법이 있는데 내가 가장 단순한 방법만 생각하려 했던 점.
   이 부분은 내가 계속해서 공부하고, 문제를 풀어가면서 알아봐야 할 내용이라고 생각한다. 추후에 정리하는 글을 만들어도 괜찮지 않을까 싶다.