[백준] 17103번(골드바흐 파티션)

백준 17103번

최종 제출 코드

import sys
input = sys.stdin.readline

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

T = int(input().rstrip())

for k in range(T):
  number = int(input().rstrip())
  cnt = 0
  if number == 4: cnt += 1
  for l in range(3, number//2+1, 2):
    if prime[l]==1 and prime[number-l]:
      cnt += 1
  print(cnt)

◼ 골드바흐의 추측 문제와 비슷

• 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
• 짝수인 소수는 2밖에 없고, 두 소수의 합으로 이루어진 짝수 중 2를 포함할 수 있는 경우는 2+2=4 밖에 없다. (2를 제외한 모든 짝수는 소수가 아니기 때문)
• prime을 탐색하는 반복문에서 입력값이 4인 경우를 위해 실행시간을 희생하기는 비효율적
  ⇒ 입력값이 4인 경우만 따로 처리해주고, 그 외의 입력값에 대해서는 인덱스 값이 홀수인 경우만 탐색하도록 함