[백준] 골드바흐 파티션

출처:: www.acmicpc.net/problem/17103

분류::

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

#골드바흐 파티션
#https://www.acmicpc.net/problem/17103
import sys
import math
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
t=int(input())
maxv= 1000000
sosu=[True]*(maxv+1)
for i in range(2,int(math.sqrt(maxv))+1): #에라토스테네스의 체로 소수배열 구해두기
    if sosu[i]:
        j=2
        while i*j<=maxv:
            sosu[i*j]=False
            j+=1
def gold_partition(n):
    cnt=0
    for i in range(2,n+1):
        if i>n-i:
            break
        if sosu[i]==True and sosu[n-i]==True: # 두 소수의 합
            cnt+=1
    return cnt
for _ in range(t):
    n=int(input())
    print(gold_partition(n))

 

3. 오답원인

 

4. 알게된 점