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

 

1. 문제

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

2보다 큰 짝수 n 이 주어졌을 때, n 의 골드바흐 파티션을 출력하는 프로그램을 작성하시오
가능한 n 의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다 
T : 테스트 케이스의 개수, 4 <= n <= 10,000 

 

 

2. 접근 방식

* 소수를 구하는 함수를 만든다 - 에라토스테네스의 체 

* 골드바흐 파티션을 구하는 함수를 만든다

* T 를 입력 받고, n 의 파티션을 구한다

 

참고) 에라토스테네스의 체

2부터 차례로 배수를 지워서 소수를 구하는 알고리즘 

출처 위키백과

소수가 아닌 경우에는 제곱근을 기준으로 대칭인 약수를 가지고 있기 때문에

ex. 16 의 약수 1, 2, 4, 6, 16 -> 1*16, 2*8, 4*4, 8*2, 16*1 

num % i == 0 의 범위를 제곱근까지만 구하면 복합도를 줄일 수 있다

def eratosthenes(num):
	# 0 부터 num 까지의 모든 수를 소수라고 가정 
    isPrime = [True] * (num+1)
    
    # 0 과 1 은 소수가 아니므로 False 로 설정 
    isPrime[0] = isPrime[1] = False 
    # 2 부터 제곱근+1 까지 범위 설정 
    for i in range(2, int(num**0.5)+1):
    
    # 소수의 배수들을 모두 False 로 변경 
    # i*i 보다 작은 수들은 이미 지워졌으므로 i*i 부터 확인
        if isPrime[i]:
            for j in range(i*i, num+1, i):
                isPrime[j] = False
    return isPrime

 

골든바흐 파티션 구하기 

def goldenbach(n, isPrime):
    # 가장 가까운 소수들의 합을 구하는 것이니 n//2 부터 1 까지 
    # isPrime[i] 과 isPrime[n-i] 이 소수인지 확인 
    for i in range(n//2, 1, -1):
        if isPrime[i] and isPrime[n-i]:
            return i, n-i
    # 적합한 소수가 없을 경우는 None 반환
    return None

 

그리고 나서 메인

# 에라토스테네스의 체를 사용하여 10000 까지 소수 여부 판별해놓기 
isPrime = estostenes(10000)

# Test Case 개수 입력 받기 
T = int(input())

# Test Case 개수만큼 n 을 입력 받고 각 n 에 대한 골든바흐 파티션 구하기

# 골든바흐 파티션 결과를 저장할 배열 선언 
result = []
for _ in range(T):
    n = int(input())
    a, b = goldenbach(n, isPrime)
    result.append(f"{a} {b}")

print('\n'.join(result))

 

여기서 result.append(f"{a} {b}") 는 f-string 을 사용하여

a, b 의 값을 문자열로 포맷팅하여 ['a' 'b'] 형식으로 리스트에 추가한다 

print('\n'.join(result)) 

T 가 3 일 경우 result 는 ['a b' 'c d' 'e f'] 형식으로 저장되어 있는데

이 문자열을 \n (줄바꿈) 구분자로 join 하여 하나의 문자열로 바꾸어 준다 

 

전체 코드 

def estostenes(num):
    isPrime = [True] * (num+1)

    isPrime[0] = isPrime[1] = False
    for i in range(2, int(num**0.5)+1):
        if isPrime[i]:
            for j in range(i*i, num+1, i):
                isPrime[j] = False

    return isPrime

def goldenbach(n, isPrime):

    for i in range(n//2, 1, -1):
        if isPrime[i] and isPrime[n-i]:
            return i, n-i
    return None

isPrime = estostenes(10000)

T = int(input())

result = []
for _ in range(T):
    n = int(input())
    a, b = goldenbach(n, isPrime)
    result.append(f"{a} {b}")

print('\n'.join(result))