백준 17103번 골드바흐 파티션 python

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

골드바흐 파티션 : (2보다 큰)짝수 N을 두 소수의 합으로 나타내는 표현

4 = 2+2
6 = 3+3
24 = 13+11 , 17+7 ...
진짜네?
그리고 한 개의 쌍이 아닐 수도 있다.

문제가 요하는 것은 2보다 큰 짝수가 몇개의 소수의 합으로 표현될 수 있는지 개수 출력하기.

N의 범위가 1,000,000 으로 크기 때문에 에스토라테네스의 체를 이용하여 소수만을 미리 분별하는 방법으로 구현했다.

해결 로직

0. 리스트를 생성하고, 에라토스테네스의 체를 이용하여 소수를 미리 걸러놓음.
1. 테스트 케이스 개수 입력받기
2. 테스트 케이스 개수만큼 N 입력받기.
3. i + N-i = N 라는 점을 이용하여 li[i] 와 li[N-i] 둘다 소수라면 count를 증가시켜 출력.
   (이때 가운데를 중심으로 좌우가 대칭이기에 N의 절반 + 1까지만 체크함.)

해답

import sys

li = list(1 for _ in range(1000001))
li[0] = 0
li[1] = 0
for i in range(2, 1000001):
    if li[i]:
        for j in range(i * 2, 1000001, i):
            li[j] = 0
        
T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    
    count = 0
    for i in range(2, N // 2 + 1):
        if (li[i] and li[N - i])== 1:
            count += 1
            
    print(count)