BOJ-9020 (Silver I)

소수판별 문제에서의 핵심은 기본적으로 소수판별횟수를 얼마나 줄일수 있냐인것같다. 우선 n이 제한된 이상 앞선 4948번의 베르트랑 공준 문제에서 해결한 것 처럼 미리 범위내 소수를 모두 리스트업 해둔 후에 계산하는 것이 효율적일 것 같다.

그 후 n을 이루는 두개의 소수, 골드바흐 파티션을 찾아내는 방법에 여러가지가 있을 것 같은데 생각나는 가장 간단할 것 같은 방법은 리스트 요소를 [0] 부터 n에서 빼가면서 뺀 나머지가 소수인지(리스트안에 들었는지)를 판별하는 것이다. 그렇게 해서 둘다 소수라면 출력한다.

import sys

def is_prime(x):
  if x==1: return False
  sq = int(x**0.5)

  for i in range(2, sq+1):
    if x%i==0: return False
  
  return True

# 값들어올때마다 반복하지 말고 미리 제한범위내 모든 #소수를 미리 계산
num_list = []
for i in range(1,10000):
  if is_prime(i): num_list.append(i)


T = int(sys.stdin.readline())
for i in range(T):
  n = int(sys.stdin.readline())
  for j in num_list:
    if n-j in num_list:
      print(j, n-j)

 

바로 해결되리라 생각했는데 생각못한 문제가 있었다. 골드바흐 파티션이 여러개 있을 수 있다는 걸 못읽었다.

답이 여러개 출력되더라.

 

로직을 바꿨다. 두 값의 차이가 가장 작은 걸 출력하기 위해서 입력값의 중앙에서부터 소수인지를 판별.

import sys

def is_prime(x):
  if x==1: return False
  sq = int(x**0.5)

  for i in range(2, sq+1):
    if x%i==0: return False
  
  return True

# 값들어올때마다 반복하지 말고 미리 제한범위내 모든 #소수를 미리 계산
num_list = []
for i in range(1,10000):
  if is_prime(i): num_list.append(i)


T = int(sys.stdin.readline())
for i in range(T):
  n = int(sys.stdin.readline())
  half = n//2
  for x in range(half, 1, -1):
    if (n-x in num_list) and (x in num_list):
      print(x, n-x)
      break