백준 9020 골드바흐의 추측 (파이썬)

풀이

import sys; import math

# 소수인지 판별하는 함수
def is_prime(x):
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True

for tc in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())

    # 효율적으로 답을 찾기위해 반으로 나누어 left와 right로 나누어 판별
    left = N//2
    right = N - left
    rst = [0, 0]
    while left > 0:
        if is_prime(left) and is_prime(right):
            print(left, right)
            break
        left -= 1
        right += 1

 

---

해설

• 소수를 판별할 수 있다면 쉽게 풀 수 있다.
• 예전에 소수를 판별하는 문제를 풀어봐서 소수 판별 함수를 다시 보긴했다..
• left, right를 나누어서 투 포인터 방식으로 답을 찾아간다.