백준 파이썬 6588 골드바흐의 추측

🚀접근하기

소수문제의 끝판왕... 생각보다 어려웠다. n을 만들 수 있는 여러가지의 방법들 중에 b-a가 가장 큰 것을 출력해야 한다는 것이 조금 까다롭게 느껴졌다. 그래도 일단 리스트를 생성해서 소수와 소수가 아닌 것들을 구분해야겠다는 생각을 했다!

 

🎉코드

import sys

n = 1000001
array=[True]*n

for i in range(3, int(len(array) ** 0.5) + 1, 2):
    if array[i]:
        for j in range(i*2, n, i):
            array[j] = False

while True:
    num = int(sys.stdin.readline())
    if num ==  0:
        break
    for i in range(3, int(num/2) + 1, 2):
        if array[i] and array[num-i]: #최대한 i가 작은 값이여야 하므로 
            #작은 값부터 반복문 시작해서 둘 다 소수인 처음 경우가 답이됨
            print(f'{num} = {i} + {num-i}')
            break
    else:
        print("Goldbach's conjecture is wrong.")

 

혼자서 다 작성한 것은 아니고, 다른 분들의 코드를 조금씩 참고하였다. (시간초과 문제로 ㅜㅜ) 

일단 True, False를 통해 소수인 것과 (True), 소수가 아닌 것 (False)을 구분해주었다. 여기서 참고한 코드 부분이 반복문을 3부터 시작해서 2씩 커지게 하는 for i in range(3, int(len(array) ** 0.5) + 1, 2): 이 부분이었는데, 애초에 0,1,2와 짝수들은 판단대상이 아니므로 홀수의 배수들만 False처리를 해주면 시간을 확실히 절약할 수 있어 되게 놀라웠다!

 

그 다음엔 똑같이 3부터 2씩 커지는 반복문을 사용하여 array[i] 값과 array[num-i]값이 모두 소수이면 출력해주는 식으로 작성해주었다. 여기서 최대한 i가 작은 소수 값이어야 하므로 작은 값부터 반복문을 시작해서 둘 다 소수인 처음 경우가 답이 되는 원리로 코드를 작성하였다.

 

 

💪다짐

저번처럼 시간을 단축하기 위해 input 말고도 sys.stdin.readline()을 사용하여 빠르게 입력을 받을 수 있는 방법을 사용해야겠다!

또한 시간이 비교적 오래걸리는 반복문을 돌릴 때에도 가장 시간이 효율적인 코드를 작성하도록 노력해야겠다.