백준 17103번 골드바흐 파티션

1. 문제 설명

문제링크

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

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

• 입력
  • 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
• 출력
  • 각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 문제에서 주어지는 정수의 가장 큰 값
p = 10 ** 6

# 소수인지 아닌지 판별하기 위한 배열
prime = [False, False] + [True] * (p - 1)

# 에라토스테네스의 체를 이용
for i in range(2, int(p ** 0.5) + 1):
    if prime[i]:
        for j in range(2 * i, p + 1, i):
            prime[j] = False

# 테스트의 개수입력
for _ in range(int(input())):
    # n값 짝수 입력
    n = int(input())

    # 골드바흐 파티션의 개수을 위한 변수
    cnt = 0

    # 파티션의 개수 중 중복을 제거 하기위해 n // 2 + 1 까지만 실행
    for i in range(2, (n // 2) + 1):
        # 합이 소수라면
        if prime[i] and prime[n - i]:
            # 카운트
            cnt += 1
    # 출력
    print(cnt)

3. 회고

Q. 문제를 보고 든 생각

• 두 소수의 순서만 다른 것은 같은 파티션이다. 이 문구를 보고 즉 중복을 제거 하라는 뜻인데
• 중복을 어떻게 하면 제거 할수 있을까??(핵심) 라는 생각 부터 들었다.
• 중복을 제거 하기 위한 방법중 반복문으로 n값 까지 돌릴때 n의 값 범위를 줄이면 중복을 제거 할수 있지 않을까? 라는생각을 했다

for i in range(2, (n // 2) + 1):
    
    if prime[i] and prime[n - i]:
        
        cnt += 1

이렇게 n의 범위를 줄여서 반복문을 돌리면 중복을 제거해서 파티션의 개수를 파악 할수 있다.

4. 아쉬운 점 혹은 고쳐야 할점

조금더 좋은 방식이 있다면 댓글로 남겨주세요.