[백준] 6588번 (python 파이썬)

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

import sys

while True:
  N = int(sys.stdin.readline().strip())
  if N == 0: 
    break
  
  prime_number = [True] * (N+1)
  prime_number[0] = prime_number[1] = False

  m = int(len(prime_number) ** 0.5) + 1
  for i in range(2, m):
    if prime_number[i]:
      for j in range(i+i, N+1, i):
        prime_number[j] = False      

  m = N // 2 + 1
  for i in range(3, m):
    if prime_number[i] and prime_number[N-i]:
      print(f'{N} = {i} + {N-i}')
      break
  else:
    print("Goldbach's conjecture is wrong.")

 

에라토스테네스의 체를 이용해서 소수를 판별하고

a + b = N 이 되는 a와 b(= N-a)가 소수인지 확인 후, 출력하는 코드이다.

 

하지만 시간초과가 나왔다.

 

여기서 사용할 트릭이 있다.

바로...데이터 미리 만들기! 이다.

 

위의 코드는 사용자로부터 숫자를 입력받는 횟수만큼 에라토스테네스의 체를 만든다.

하지만 그 경우 너무 비효율적이다.

입력 조건을 보면 입력될 숫자의 최대값이 백만이다.

따라서 미리 백만개로 에라토스테네스의 체를 만들어 놓고 그걸 재사용하는 방법을 쓰는게 좋다.

 

import sys

prime_number = [True] * 1000001
prime_number[0] = prime_number[1] = False

for i in range(2, 1001):
  if prime_number[i]:
    for j in range(i+i, 1000001, i):
      prime_number[j] = False      

while True:
  N = int(sys.stdin.readline().strip())
  if N == 0: 
    break
      
  m = N // 2 + 1
  for i in range(3, m):
    if prime_number[i] and prime_number[N-i]:
      print(f'{N} = {i} + {N-i}')
      break
  else:
    print("Goldbach's conjecture is wrong.")