[백준] 6588번(골드바흐의 추측)

백준 6588번

제출코드(시간초과)

import sys
input = sys.stdin.readline

prime = [1]*1000001
prime[0] = 0
prime[1] = 0
prime_list = []

for i in range(2, int(1000000**0.5)+1):
  if prime[i] == 1:
    for j in range(i*2, 1000001, i):
      prime[j] = 0

while True:
  num = int(input().rstrip())
  if num == 0: break
  
  for k in range(len(prime)//2):
    if k in prime_list and (num-k) in prime_list:
        print(f'{num} = {k} + {num-k}')
        break
  else:
    print("Goldbach's conjecture is wrong.")

◼ 에라스토테네스의 체 활용

• 입력값의 범위가 큰만큼 소수의 리스트를 만들어서 푸는 것이 가장 빠를 것이라고 판단
  ⇒ 시간초과가 떠서 아래의 코드 추가

for l in range(len(prime)):
  if prime[l] == 1:
    prime_list.append(l)

• prime_list는 최초로 코드를 실행할 때 한 번만 생성하면 되므로 매번 prime을 탐색하는 것보다 빠를 것이라고 판단
  ⇒ 시간초과

최종 제출 코드

import sys
input = sys.stdin.readline

prime = [1]*1000001
prime[0] = 0
prime[1] = 0
prime_list = []

for i in range(2, int(1000000**0.5)+1):
  if prime[i] == 1:
    for j in range(i*2, 1000001, i):
      prime[j] = 0

while True:
  num = int(input().rstrip())
  if num == 0: break

  for k in range(3, num, 2):
    if prime[k]==1 and prime[num-k]==1:
        print(f'{num} = {k} + {num-k}')
        break
  else:
    print("Goldbach's conjecture is wrong.")

◼ 입력값이 홀수 소수의 합인지를 검사하는 반복문 수정

• 홀수 소수의 합이라는 점을 활용해 for문을 for k in range(len(prime)//2)에서 for k in range(3, num, 2)로 수정했더니 정답...