6588 Python 골드바흐의 추측 모든 순열

문제 

6588번: 골드바흐의 추측

 

import math
import sys

# 테스트 케이스 갯수
maxValue = 1000000
lists = [True] * (maxValue + 1)
lists[0] = lists[1] = False

# 에라토스테네스의 체
for i in range(2, int(math.sqrt(maxValue) + 1)):
    if lists[i]:
        # 1. 시간 초과 나서 추가한 내용 => 한 번 확인한 내용은 다시 확인하지 않아도됨 아니면 같은 일을 반복하는 것이기 때문
        # 2. 다음과 같은 경우로 사용을 하면 아래 코드보다 시간이 오래걸림
        # while i * j <= maxValue:
        #     lists[i * j] = False
        #     # 짝수 및 소수가 아니면 다 False
        #     j += 1
        for j in range(i * i, maxValue + 1, i):
            lists[j] = False  # 3. 배수의 모든 값들을 False 로 변경 i*(i+i)

while True:
    n = int(sys.stdin.readline())

    # 0 이면 break
    if n == 0:
        break
    check = False

    # 계산 로직
    for i in range(3, n, 2): 
        # 문제 해결 => 3~n까지 +1씩 확인하지 않고 +2씩 확인함. 
        if lists[i] and lists[n - i]:
            print(str(n) + " = " + str(i) + " + " + str(n - i))
            check = True
            break

    # 두 홀수 소수의 합으로 나타낼 수 없는 경우
    if not check:
        print("Goldbach's conjecture is wrong.")

 

해결 과정

1. if 코드를 추가하여 한 번 확인한 값은 다시 확인하지 않도록 => 명확한 문제 해결은 아니었지만, 필요한 부분이었음.

2.  while문을 통해 에라토스테네스 체로 소수를 구하면 for 문을 사용하는 것보다 시간이 오래걸린다는 블로그를 참조 ! => 똑같은 시간 초과 에러 !

3. 마지막으로 계산로직에서 n을 1을 더하여 하나하나 확인하는 것에서 짝수는 확인하지 않고 홀수만 확인하기 위해 2을 더하여 절반으로 값을 줄여 진행하니 시간 초과 에러 해결 성공 !

 

문제 풀이

많은 시행착오가 있었지만, 작은 코드 하나가 시간초과 문제가 될 수 있어 섬세하게 접근해야한다는 것을 되새기게 되었다.