[백준 문제풀이] 17103 - 골드바흐 파티션

백준 문제풀이 17103번

풀이

골드바흐의 추측이란 ‘2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다’를 말한다. 짝수 N을 두 소수의 합으로 나타내어 골드바흐 파티션인지 알아내려면, 미리 소수를 가진 배열을 구하고 and문을 사용해 j와 N-j가 둘 다 참인 구문을 사용하면 알아낼 수 있다. 이 때 반복문 j열에서 범위를 N으로 둔다면 중복된 값이 발생하므로, $N//2 + 1$로 값을 제한해준다.

코드

import sys

input = sys.stdin.readline

# 에라토스테네스의 체로 미리 소수를 담아두는 배열을 만듬
arr = [0] * 2 + [1] * 999999
for i in range(2, 1000001):
    if arr[i]:
        for j in range(i * 2, 1000001, i):
            arr[j] = 0

T = int(input())  # 테스트 케이스

for i in range(T):
    count = 0  # 정답을 담을 변수
    N = int(input())
    for j in range(2, N//2+1):
        if arr[j] and arr[N - j]:
            count += 1
    print(count)