[알고리즘][백준] 17103번 골드바흐 파티션 - 파이썬(python) 풀이

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

17103번: 골드바흐 파티션

---

6588번 골드바흐의 추측을 응용한 문제이다

 

1,000,000개의 수를 매번 소수인걸 확인하기엔 메모리사용이 엄청나기 때문에 먼저 에라토스테네스의 체를 사용하여 소수를 구별한다.

import sys

t = int(sys.stdin.readline())

sosu = [True] * 1000001
for i in range(2, int(len(sosu)**0.5)+1):
    if sosu[i]:
        for j in range(2*i, 1000000, i):
            sosu[j] = False

for _ in range(t):
    n = int(sys.stdin.readline())
    cnt = 0
    for i in range(2, n//2+1):
        if sosu[i] and sosu[n-i]:
            cnt += 1
    print(cnt)

17103_골드바흐파티션.py

0.00MB