[BOJ] 17103 | 골드바흐 파티션

문제링크

---

17103 | 골드바흐 파티션

풀이과정

---

[BOJ] 9020 | 골드바흐의 추측이랑 비슷한 문제다.

에라토스테네스의 체를 이용해서 미리 소수 판별을 해두고 두개를 더할 때 둘 다 소수라면 결과값에 1을 추가해줬다.

여기서 파티션 중복을 잘 생각해줘야하는데, 입력값 10의 경우를 살펴보자.
소수끼리의 합을 볼 때 3 + 7, 5 + 5, 7 + 3이 있는데 3과 7의 덧셈 조합은 같은 파티션으로 본다.

그래서 생각한건, 입력한 값의 절반 이상의 값은 고려하지 않는 것이다. 그러면 7+3은 결과에 추가되지 않는 셈이다.

코드

---

import sys

T = int(input())

primes = [True] * 1000001
for i in range(2, 1000001):
    if primes[i] == True:
        for j in range(2*i, 1000001, i):
            primes[j] = False

for _ in range(T):
    result = 0
    n = int(sys.stdin.readline().rstrip())
    
    for i in range(2, n // 2 + 1):
        if primes[i] and primes[n - i]:
            # print('두 소수 더해도 돼', i, n-i)
            result += 1
    
    print(result)

결과

---