greentea31's Note

https://www.acmicpc.net/problem/17103

풀이 과정

https://greentea31.tistory.com/15

위의 문제와 유사하게 해결할 수 있다. 100만 이하의 수에 대해 에라토스테네스의 체로 모든 소수를 찾은 다음 입력 수 - 찾은 소수 == 소수 이면 골드바흐 파티션 변수를 1 늘려주는 식으로 해결할 수 있다. 

위는 N이 12일때 골드바흐 파티션의 개수를 구하는 예시이다.

소스 코드

import sys

prime = []
check = [0] * 1000001
check[0] = 1
check[1] = 1

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

T = int(sys.stdin.readline())

for _ in range(T):
    count = 0
    N = int(sys.stdin.readline())
    for i in prime:
        if i >= N:
            break
        if not check[N - i] and i <= N-i:  # 순서만 다른거 counting 하지 않기 위해
            count += 1
    print(count)