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

2021.12.03

백준 9020 골드바흐의 추측

def prime(x):                  # 소수 판별 함수
    if x == 1:
        return False
    else:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                return False
        return True
    
def goldhach(x):             # 골드바흐 파티션 중 두 수의 차이가 가장 작은 값
    for i in range(int(x/2),1,-1):
        if prime(i):
            for j in range(2,x):
                if (i + j) == x and prime(j):
                    return [i , j]

T = int(input())             # 테스트 케이스 

for i in range(T):
    n = goldhach(int(input()))
    for i in range(2):
        print(n[i], end = ' ')

 처음에 푼 코드

그런데 이 코드는 시간이 너무 걸렸다

골드바흐 함수를 정의하는데 for문과 범위에 쓸모없는 수들이 포함돼서 그랬다.

 

def prime(x):                  # 소수 판별 함수
    if x == 1:
        return False
    else:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                return False
        return True
    
def goldhach(x):          # 골드바흐 파티션 중 두 수의 차이가 가장 작은 값
    arr = [2] + list(range(3,(x//2)+1,2))
    for i in reversed(arr):
        if prime(i):
            if prime(x-i):
                return [i , x-i]

T = int(input())             # 테스트 케이스 

for i in range(T):
    n = goldhach(int(input()))
    for i in range(2):
        print(n[i], end = ' ')

 수정한 코드

이 코드가 처음 코드보다 시간 측면에서 7배 빠르다.

우선 소수 판별 함수에서 주어진 수가 2부터 1씩 커지는 숫자를 넣어서 나누었을 때

나머지가 0이면 False를 리턴 아닌 경우 소수이므로 True를 리턴한다.

범위를 x**0.5까지 한정한 이유는 수학적으로 x의 제곱근의 배수까지 지우면

 

x이하의 소수만 남게 되기 때문이다. (에라토스테네스의 체를 참고)

 

위 두 코드의 차이는 골드바흐 함수 정의에 차이가 있는데

짝수 n이 소수 M 과 N의 합으로 나타낼 수 있으며 M과 N의 차이가 가장 적은 값을 구할 때

소수가 2를 제외하고는 모두 홀수인 점과 M, N의 차이가 가장 적은 값은 n/2 값부터 역순으로

적용해보면 찾을 수 있다는 점을 통해 구하는 범위를 더 좁게 한정 시킬 수 있었고

n = M + N 즉 n - M = N 이라는 것을 통해서 for문 하나를 단축시킬 수 있었다.