[Python] BOJ 9020 : 골드바흐의 추측

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

위는 문제 링크입니다. 

 

* 골드바흐의 추측 문제 요구사항 

• 짝수를 두 소수의 합으로 나타내는 표현 (= 골드바흐 파티션)
• 두 소수의 차이가 가장 작은 것들을 출력
  • 두 수 중 작은 수부터 출력 
    • ex) 8 = (3 + 5), (1 + 7)  두 가지 경우의 수 중 두 수의 차이가 적은 3과 5를 출력할 것
  • 정수 안에서 두 수의 합으로 짝수를 표현할 때, 그 차이가 가장 적은 경우의 수는 짝수를 2로 나눈 값이다. 
    • ex) 8 / 2 = 4, 4 + 4, 차이가 0이니 가장 작다고 볼 수 있다. 

* 골드바흐의 추측 설계

• 소수 판별 함수를 작성한다. 
  • base case == 1: 
    • False
  • 2부터 주어진 N의 제곱근 + 1 까지 
    • N 의 나머지가 0이라면 
      • False
  • return True
• num 에 짝수를 받는다. (주어진 테스트 케이스 만큼 받을 수 있게 for 문을 사용한다.)
• A = num // 2, B = num //2 ( 짝수를 2로 나누었을 때, 소수가 아니라면 그 값들을 감소시키거나 증가시켜야 된다.)
• 감소되거나 증가된 수가 소수인지 판별한다. 
  • 맞다면 A와 B를 출력 후 break 
  • 아니라면 
    • A와 B 를 감소시키고 증가시켜 다음 수를 찾아본다.

* 구현 

import math 

def isPrime(N):
    if N == 1:
        return False
    
    for i in range(2, int(math.sqrt(N) + 1)):
        if N % i == 0:
            return False
    
    return True

N = int(input())

for _ in range(N):
    num = int(input())

    A = num // 2
    B = num // 2

    for _ in range(num//2):
        if isPrime(A) and isPrime(B):
            print(A, B)
            break 
        else:
            A -= 1
            B += 1