IP
1.230.0.0
Created
12-28 12:59
1
import sys
2
input = lambda: sys.stdin.readline().rstrip()
3
MAX = 1_000_000
4
5
def get_prime():
6
# 기본적으로 True로 초기화 하고, 배수에 해당하는 인덱스를 False로 변경
7
primes = [True] * (MAX + 1)
8
# 0과 1은 소수가 아님
9
primes[0] = primes[1] = False
10
11
# 에라토스테네스의 체 이용하여 소수 판별
12
# 어떤 소수는 1과 자기자신을 제외하면 최대 약수의 값이 √n 이하기 때문
13
for i in range(2, int(MAX**0.5) + 1):
14
if primes[i]:
15
for j in range(i * i, MAX + 1, i):
16
primes[j] = False
17
18
return primes
19
20
# 테스트케이스 수 입력
21
t = int(input())
22
23
# 모든 테스트케이스에서 공통적으로 사용할 소수 목록
24
primes = get_prime()
25
26
answer = []
27
for _ in range(t):
28
n = int(input())
29
result = 0
30
31
# n을 두 소수의 합으로 나타내는 방법의 수 계산
32
# a와 b의 합을 구하기 때문에 a(i)가 n의 절반까지만 검사
33
# (a와 b의 순서가 바뀌어도 같은 경우이기 때문)
34
for i in range(2, n // 2 + 1):
35
# n에 대해 a와 b의 합을 구하는 데,
36
# a가 i라면, b는 n-i가 되기 때문.
37
if primes[i] and primes[n - i]:
38
result += 1
39
40
answer.append(result)
41
42
# 모든 테스트케이스에 대한 결과를 일괄 출력
43
print('\n'.join(map(str, answer)))