17103: 골드바흐 파티션

시간 제한	메모리 제한
0.5초	512MB

문제

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

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

 

입력

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

 

출력

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

 

---

풀이

시간 제한 0.5초의 빡빡한 문제다. 어지간한 소수 찾기 알고리즘은 시간 초과가 뜬다. 테스트 케이스가 입력 될 때마다 소수를 따로 찾는 방법으로는 절대 AC 안 뜰테니 전체 N 범위인 1,000,000까지의 소수를 미리 찾아놔야 한다. 에라토스테네스의 체를 활용해 소수를 찾아줬다.

 

범위 내의 소수를 찾는 것은 고정시간이 걸리므로 일단 패스. 이후 테스트 케이스마다 골드바흐 파티션을 어떻게 찾을 것인가를 고민해야 한다.

 

N을 입력 받고 소수 배열을 하나씩 차례로 확인해서 N - prime[i]의 결과가 소수라면 골드바흐 파티션이다. 이 때 prime[i]가 N/2보다 크면 더 이상 탐색을 실시하지 않아도 된다. N이 10일 때 7 + 3과 3 + 7은 같은 경우로 치기 때문에 10 - 5까지만 확인해보면 된다. 이렇게 시간을 아낄 수 있으나 한 가지 더 필요하다.

 

N - prime[i]가 소수인지 확인할 때 배열에서 N - prime[i]를 찾는 것이다. 가장 빠른 것은 해시 맵을 사용하는 것이다. 1,000,000 길이의 배열이 좀 크긴 하지만 그래도 넉넉한 512MB를 이렇게 활용해줘야 탐색 시간을 O(1)로 줄일 수 있다. 소수 찾을 때 썼던 체를 그대로 재활용할 수 있다.

 

 

정답 코드

import sys

sieve = [True] * 1000001
prime = []
sieve[0] = False
sieve[1] = False
for i in range(2, 1000001):
    if sieve[i]:
        prime.append(i)
        for j in range(i*2, 1000001, i):
            sieve[j] = False

T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    count, k = 0, 0
    for p in prime:
        if p > int(N / 2):
            break
        if sieve[N - p]:
            count += 1
    print(count)