BOJ 9020번 : 골드바흐의 추측

안녕하세요. 지난 포스팅의 BOJ 4948번 : 베트트랑 공준에서는 에라토스테네스의 체의 개념을 설명하고 실제로 구현해보았습니다. 오늘은 소수 관련 마지막 문제로 골드바흐의 추측에 대한 문제를 풀어보도록 하겠습니다. 지금까지 활용했던 소수 판별법을 적용하면 되기 때문에 크게 어렵지는 않습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력
• 소수 판별 알고리즘

 

제출 코드

import math

def is_prime(number) :
    for n in range(2, int(math.sqrt(number)) + 1) :
        if number % n == 0 or number == 1 : return False
    
    return True

for _ in range(int(input())) :
    N = int(input())
    p = N // 2
    while True :
        if is_prime(p) : 
            q = N - p
            if is_prime(q) :
                print(p, q)
                break
            else :
                p -= 1
        else :
            p -= 1

 

해설

일단 입력은 테스트케이스의 개수를 입력받고 아랫줄부터 각 테스트케이스 예제를 입력받습니다. 저희의 목표는 각 테스트케이스에 대해서 문제에서 명시한 골드바흐 파티션을 출력하는 것입니다. 이때, 하나의 숫자에 대한 여러 개의 골드바흐 파티션이 존재하면 두 소수의 차이가 가장 작은 것을 출력하면 되죠. 

 

기본적으로 위 코드의 작동방식은 아래와 같습니다. 

 

STEP1. 입력된 숫자 $N$의 절반을 $p$라고 하자. 

STEP2. $p$가 소수인지 검사한다. 

STEP3. $p$가 소수가 아니라면 $p$에서 1을 뺀 뒤 다시 STEP2로 돌아간다.

STEP4. $p$가 소수라면 $q = N - p$를 계산한 뒤 소수인지 검사한다. 

STEP5. $q$가 소수가 아니라면 $p$에서 1을 뺀 뒤 다시 STEP2로 돌아간다.

STEP6. $q$가 소수라면 $p$와 $q$를 출력한 뒤 반복문을 탈출한다. 

 

위 코드는 복잡해보이지만 사실 쉬운 동작을 보유합니다. 소수 판별은 지난 포스팅에서 했던 방식과 동일하기 때문에 자세한 설명은 생략하도록 하겠습니다. 

 

참고자료 및 그림출처

백준 코딩 문제