[백준 - python] 0920번: 골드바흐의 추측

<문제 링크>

9020번: 골드바흐의 추측

 

<문제 풀이>

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


T = int(input())

for i in range(T):
    n = int(input())
    for num in range(n // 2, 1, -1):
        if check_prime(num) and check_prime(n - num):
            print(num, n - num)
            break

9020 입출력 예시

*key point: 소수 리스트를 만든 뒤 입력값을 만들 수 있는 소수 조합을 찾고 그 중 두 소수의 차이가 작은 조합을 고르는 직관적인 알고리즘을 구현한 경우 시간 초과가 발생하였다. 실행 시간을 최소화하기 위하여 소수임을 판별해주는 함수를 정의하여 사용하고, 조건에 맞는 소수 조합을 빠르고 간편하게 찾기 위해 입력값 n을 2로 나눈 수에서부터 반복을 시작하였다.