백준 / 골드바흐 파티션 / 17103

Question

문제링크
Silver 2

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
  짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

Input

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

5
6
8
10
12
100

Output

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

1
1
2
1
6

Logic

기본 구조 : 에라토스테네스의 체
1. 우선 최대 수까지 에라토스테네스의 체를 이용하여 소수 표를 미리 작성한다.
2. 주어진 수에 대해 소수 범위 내에서 골드바흐 조합을 찾아서, 수를 센다.

Code

import sys,math

#에라토스테네스의 체 코드 참조
n=1000000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            a[j] = False

for i in range(int(sys.stdin.readline())):
    num=int(sys.stdin.readline())
    cnt=0

    for j in primes:
        if j>num/2: break
        if a[num-j] : cnt+=1
    print(cnt)