[Python] 백준 파이썬 9020 골드바흐의 추측

 

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

9020번: 골드바흐의 추측

먼저 소수 판별하는 함수 정의해줌

def sosu(x):
  if x==1:
    return False
  for i in range(2, int(x**0.5) + 1):
    if x % i == 0:
      return False
  return True

이 다음은 어떻게 진행할까 하다가 처음에는 4 <= n <= 10000 범위에 있는 모든 짝수 리스트, 모든 소수 리스트 두개를 만들어서 진행함

당연히 실패 해버림... 그래서 찾아보니까 입력된 n을 반으로 나누고 하나는 점점 작아지고, 하나는 점점 커지면서 두개가 소수일 때를 출력하면 되는 거였음

# 백준 9020 골드바흐의 추측
def sosu(x):
  if x==1:
    return False
  for i in range(2, int(x**0.5) + 1):
    if x % i == 0:
      return False
  return True

t = int(input())
for i in range(t):
  n = int(input())

  # n을 반으로 쪼개서 생각
  a, b = n//2, n//2
  while a > 0:
    if sosu(a) and sosu(b):
      print(a, b)
      break  # a, b 둘 다 소수면 출력하고 끝.
      
    # 아니면 a는 1씩 빼주고 b는 1씩 더해줌
    else: 
      a -= 1
      b += 1