[Python] 백준 9020번 골드바흐의 추측

 

 

 

 

# 골드바흐의 추측
import sys

def is_prime(A):
  if A < 2:
    return False
  for i in range(2, A):
    if A % i == 0:
      return False
  return True

T = int(sys.stdin.readline())
for _ in range(T):
    P = int(sys.stdin.readline())

    B = P // 2
    C = P // 2

    for _ in range(P // 2):
      if is_prime(B) and is_prime(C):
        print(B, C)
        break
      else:
        B -= 1
        C += 1

 

 

소수를 구하는 문제같은 경우는 코드를 어떻게 짜야하는지 이해하면 어렵지 않고 함수로 만들어볼 수 있다.

 

def is_prime(A):

A가 2보다 작으면 소수가 아니니까 False 를 반환한다.

(처음에는 A==1이면 False를 반환하라고 작성했었는데, 2보다 작은 수를 제외하는게 더 정확한 표현이다.)

그리고 A를 2부터 A까지 차례대로 나눠본다.

만약에 나머지가 0이면 False를 반환한다. A보다 작은 수로 나눴을 때 나머지 없이 나눠지면 소수가 아니기 때문.

그리고 이외 경우 소수로 True를 반환한다. 

 

 

테스트 코드 T번 입력할 수 있는 입력 창을 만들고,

for문을 통해 골드바흐 파티션을 출력한다.

 

먼저 짝수를 입력받는다.

변수를 2개 선언하고, 짝수를 반으로 나눠 각 각 변수에 넣는다. (B, C = P//2, P//2)

한번 더 for 문을 돌려서 

 반으로 나눈 수가 소수인 경우에 바로 출력 후 break

 안나눠지는 경우 B-1, C+1 해서 가장 차이 안나는 소수를 찾도록 만든다.