[백준/Python] 17103 골드바흐 파티션

[백준/Python] 17103 골드바흐 파티션

정답 코드 및 설명

def sieve_of_eratosthenes(n):
    prime = [True for _ in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return [p for p in range(2, n+1) if prime[p]]

def goldbach_partitions_count(n, primes_set):
    count = 0
    for p in primes:
        if p > n // 2:
            break
        if (n - p) in primes_set:
            count += 1
    return count

# 주어진 범위 내의 모든 소수를 찾기
max_num = 1000000
primes = sieve_of_eratosthenes(max_num)
primes_set = set(primes)

# 테스트 케이스를 입력받고 결과를 계산
T = int(input())
for _ in range(T):
    N = int(input())
    print(goldbach_partitions_count(N, primes_set))

문제 설명

• 골드바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

즉, 짝수 N을 두 소수의 합으로 나타내는 표현을 '골드바흐 파티션'이라고 한다.

짝수 N 이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자 두 소수의 순서만 다른 것은 같은 파티션이다.

문제 접근 방법

1. 제한되어있는 N 의 크기, N까지의 모든 소수를 미리 찾아 두고, 골드바흐 파티션을 찾는 데 사용한다.
2. 골드바흐 파티션을 찾는 방법

• 주어진 짝수 N에 대해 가능한 모든 골드바흐 파티션의 개수를 계산한다.
• primes 이라는 모든 소수를 포함하는 리스트를 순회하면서 각 소수 p 에 대해서 N - p 도 소수인지 확인한다.
• 소수 P + 또 다른 소수 P' = N 이라면 N - P = P' 가 될 것이기 때문
• 또한, p > n // 2 조건으로 불필요한 반복을 줄인다. 왜냐하면 N이 짝수이기 때문에 N의 절반을 초과하는 소수를 고려할 필요가 없기 때문이다.

소스코드 설명

def sieve_of_eratosthenes(n):
    prime = [True for _ in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return [p for p in range(2, n+1) if prime[p]]

위 함수는 n 까지의 모든 소수를 찾아 반환하는 함수이다. 이를 통해서 문제에 제한되어있는 N크기의 최대인 1,000,000 까지 모든 소수를 미리 찾아둔다.

def goldbach_partitions_count(n, primes_set):
    count = 0
    for p in primes:
        if p > n // 2:
            break
        if (n - p) in primes_set:
            count += 1
    return count

위 함수는 n 과 위에 구해둔 모든 소수들의 집합을 매개변수로 하여, n이 몇 개의 골드바흐 파티션을 가지고 있는 지 반환하는 함수 이다.

for p in primes:

N까지의 모든 소수를 저장한 primes 에 존재하는 모든 데이터에 대해서,

		if p > n // 2:
            break
        if (n - p) in primes_set:
            count += 1

1. p > n // 2 조건으로 불필요한 반복을 막는다. N은 2이상 짝수 이기 때문에 N의 절반을 넘는 수에 대해서 검증할 필요가 없기 때문이다.
2. n - p 가 소수라면 count 를 증가시킨다.

위 함수를 통해서 골드바흐 파티션 문제를 해결 할 수 있다.