[백준] 17103: 골드바흐 파티션 (Python)

문제📖

풀이🙏

• 에라토스테네스의 체를 이용하여 리스트에 소수가 아닌 값들을 False로 변경한다.
• 골드바흐 파티션의 개수를 구하기 위해 ( 이 때 두 소수의 순서만 다른 것은 같은 파티션 ) 판단하고 싶은 값을 입력받고 2부터 n//2+1 까지 ( 중복값은 제거됨) i, n-i가 소수일 경우 count를 1씩 증가한다.

코드💻

import sys
input = sys.stdin.readline

# 에라토스테네스의 체
# 전체 수 만큼 True 리스트 생성
# 2부터 1씩 더해주면서 그 배수에 해당하는 값들을 False로 바꾼다.
array = [True for i in range(1000001)]

for i in range(2, 1001):
    if array[i]:
        for k in range(i + i, 1000001, i):
            array[k] = False

tc = int(input())
for i in range(tc):
    n = int(input())
    count = 0
    
    for i in range(2, n//2+1):
        if array[i] and array[n-i]:
            count+=1

    print(count)