골드바흐 파티션[백준 17103]

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

 

에라토스테네스의 체를 이용해서 소수 판별을 하면 된다.

이 방법으로 다행히 시간초과는 피할 수 있다. 

test = int(input())
arr = [1 for _ in range(1000009)]
for i in range(2,1000009):
    if arr[i] == 1 :
        for j in range(i*2, 1000009, i):
            arr[j] = 0 
for _ in range(test):
    n = int(input())
    cnt = 0 
    for i in range(2, n//2+1 ):
        if arr[i]==1 and arr[n-i]==1:
            cnt += 1 
    print(cnt)