[Python] 백준 17013 골드바흐 파티션

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

17103번: 골드바흐 파티션

 

 

문제 해결

골드바흐의 추측 문제는 거의 에라토스테네스 체를 쓴 다음 가능한 짝을 찾는 문제이다.

for문 돌려서 가능한 짝을 찾는 방법이 가장 기본적인 방법.

 

 

CODE

t = int(input())
p = [True]*1000001
p[0] = False # 0, 1은 소수가 아니다.
p[1] = False
for i in range(2,1000001):
    if p[i]:
        for j in range(i+i,1000001,i): #j는 i의 배수
            p[j] = False  #소수 i의 배수이므로 False
for _ in range(t):
    n = int(input())
    cnt = 0
    for i in range(n//2+1): i<n-i 로 놓고 (i,n-i) 짝 찾기
        if p[i] and p[n-i]:
            cnt += 1
    print(cnt)