[BOJ] 17103번 - 골드바흐 파티션

---

문제설명

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

17103번: 골드바흐 파티션

사고과정

• 골드바흐의 추측 문제와 비슷하게 풀이하면 된다. 단, a, b 쌍의 개수를 구하여야 하는데, 순서가 다른 a, b도 같은 것으로 여기므로 일종의 조합을 구해야 하는 문제이다.
• 어차피 순서가 다른 것도 같은 것으로 취급하기 때문에 n = a + b 경우를 돌 때,  a가 n // 2 일 때까지만 돌면 된다!
• 참고로 처음에 array[2] = False로 해서 에라토스테네스 체에서 2의 배수가 안걸러지는 실수를 했다. 이를 모르고 백준 사이트에 질문했었다..

풀이

import sys
import math
input = sys.stdin.readline

array = [True] * (int(1e6) + 1)
array[0] = array[1] = False
for i in range(2, int(math.sqrt(1e6)) + 1):
    if array[i]:
        j = 2
        while i * j <= int(1e6):
            array[i*j] = False
            j += 1
for tc in range(int(input())):
    n = int(input())
    count = 0
    for i in range(1, n//2 + 1):
        a, b = i, n-i
        if array[a] == True and array[b] == True:
            count += 1

    print(count)