[Python] 17103. 골드바흐 파티션

문제

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

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

예제 입력 1 

5
6
8
10
12
100

예제 출력 1 

1
1
2
1
6

---

 

예제를 보고 어떤 식으로 이루어지는 지 추측해보자.

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7 = 5 + 5

12 = 5 + 7

이런 식으로 순서와 상관 없이 이루어지는 걸 구하면 된다. -> 3 + 7과 7 + 3은 하나로 본다.

 

먼저, 그 숫자까지의 소수가 어떤 수가 있는 지를 구한다. 이 때, 테스트케이스를 여러 개 받는데, 받을 때마다 소수를 찾는 것은 불필요하니,

테스트케이스 중 가장 큰 숫자를 기준으로 소수를 구하고, 처리하는 것이 시간적으로 이득이다.

data = sys.stdin.read().split()
T = int(data[0])
nums = list(map(int, data[1:]))
max_n = max(nums)

sys.stdin.read().split()
read() : EOF가 들어올 때까지 읽는다. 즉, 테스트케이스를 한번에 입력해서 받아올 수 있게 함
split() : 공백(줄바꿈도 포함)을 기준으로 나누어 파싱해줌
예제를 이 방식으로 입력했다면 아래와 같이 저장됌
data = [5, 6, 8, 10, 12, 100]

 

가장 큰 수를 이용하여 소수를 구하는 함수에 넣고 소수가 들어있는 배열을 가져온다.

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    end = int(limit ** 0.5) + 1

    for i in range(2, end):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    
    primes = [idx for idx, is_p in enumerate(is_prime) if is_p]
    return is_prime, primes
    
 `````` 위 로직들 ````````
_, primes = sieve(max_n)

enumerate
배열에 인덱스와, 값이 동시에 필요한 상황에 사용하는 내장 함수
for idx, val in enumerate(arr, start=0) ....
start 옵션을 통해 인덱스 시작 위치를 정할 수 있다.
위의 적힌 코드를 풀어서 보자면,
primes[]
for idx in range(len(is_prime)):
     if is_prime[idx]:
          primes.append[idx]
인데, 이는 인덱스(idx)와 값(is_prime[idx])을 모두 사용하기 때문에 이렇게 풀어 쓰지 않고, enumerate를 쓰는 것이 코드의 가독성과
리스트를 순회하며 동시에 인덱스와 값을 꺼내는 성질로 인해 시간적으로도 이득이다.

_, primes = sieve(max_n)
위 함수에서 나온 만들어져 나온 배열은 is_prime 과 primes 두 개로, 실제로 문제에서 사용하는 것은 primes 하나 이기 때문에 primes만 return 해도 되지만, 모든 배열을 return(언젠가 쓰일 수도 있다는 가정)한다면, _ 값으로 받는다.(여기에 들어오는 값을 의도적으로 무시한다.)

 

이제 구한 소수들을 통해, 마지막으로 소수의 합이 n 이 되는 개수를 찾는 함수를 만든다.

def count_pairs(n, primes):
    l, r = 0, len(primes) - 1
    while r >=0 and primes[r] > n: # n 보다 큰 소수들을 배제한다.
        r -= 1
    
    ans = 0
    while l <= r:
        s = primes[l] + primes[r]
        if s == n:
            l += 1
            r -= 1
            ans += 1

        elif s < n:
            l += 1 
        
        else:
            r -= 1
    return ans

 

최종적인 코드를 보면,

import sys

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    end = int(limit ** 0.5) + 1

    for i in range(2, end):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    
    # primes = []
    # for j in range(limit + 1):
    #     if is_prime[j]:
    #         primes.append(j)
    primes = [idx for idx, is_p in enumerate(is_prime) if is_p]
    return is_prime, primes

def count_pairs(n, primes):
    l, r = 0, len(primes) - 1
    while r >=0 and primes[r] > n:
        r -= 1
    
    ans = 0
    while l <= r:
        s = primes[l] + primes[r]
        if s == n:
            l += 1
            r -= 1
            ans += 1

        elif s < n:
            l += 1 
        
        else:
            r -= 1
    return ans

data = sys.stdin.read().split()
T = int(data[0])
nums = list(map(int, data[1:]))
max_n = max(nums) 
_, primes = sieve(max_n)

out = []
for n in nums:
    out.append(str(count_pairs(n, primes)))
sys.stdout.write("\n".join(out))