(Python/🥈2)백준 알고리즘 17103번: 골드바흐 파티션

백준알고리즘 골드바흐 파티션

문제 : 

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

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

 

입력 : 

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

출력 : 

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

 

import sys

t = int(input())

arr = [True for _ in range(1000001)]
for i in range(2,1001):
    if arr[i]:
        for j in range(i + i , 1000001, i):
            arr[j] = False

for i in range(t):
    res = 0
    n = int(sys.stdin.readline().rstrip())
    for j in range(2, n//2+1):
        if arr[j] and arr[n-j]:
            res += 1
    print(res)

 

 

에라토스테네스의 체를 사용한다.

만약 n이 소수들의 합 즉 arr에서 둘 다 true일때 res를 더해주면 된다.

 

 

에라토스테네스

https://windy7271.tistory.com/entry/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

에라토스테네스의 체

여기에 정리를 해놨다.