[Python]17103번, 골드바흐 파티션

문제

 

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

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

짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 

두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

 

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력

 

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

 

풀이

 

로직은 굉장히 간단하지만 계속되는 시간초과를 어떻게든 피하느라 시간이 소요됐다.

 

결과만 말하자면, 에라토스테네스의 체를 사용해 먼저 문제에서 주어진 최댓값인 1000000까지의 소수를 전부 구한 뒤

 

집합(set)으로 만들었다. 여기서 집합으로 만들지 않고 그냥 리스트로 순회하려고 하면 바로 시간초과다.

 

이어서 주어진 숫자 t만큼 반복문을 돌며

 

• 주어진 숫자가 4일 경우엔 무조건 1을 출력하고 다음 반복으로 넘어가고
• 그렇지 않을 경우 3부터 주어진 숫자의 절반까지 탐색하되, 2씩 건너뛰며 탐색했다.
  이는 2 이후의 짝수는 모두 합성수이기 때문에 가능하다.
• 골드바흐 파티션을 만날 때마다 cnt를 1씩 올려주고, 반복이 끝나면 출력.

이렇게 다소 억지스럽게 통과할 수 있었다.

import sys
import math


def eratos(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    return [x for x in range(n + 1) if is_prime[x]]


x = set(eratos(1000000))

t = int(sys.stdin.readline().rstrip())

for _ in range(t):
    a = int(sys.stdin.readline())
    if a == 4:
        print(1)
        continue
    cnt = 0
    for i in range(3, a // 2 + 1, +2):
        if i in x and a - i in x:
            cnt += 1
    print(cnt)