[python] 백준 17103번

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

문제

---

소스코드

import sys

number = [True] * 1000001

# 소수 list
for i in range(2, int(len(number) ** 0.5) + 1):
    if number[i]:
        for j in range(2 * i, 1000001, i):
            number[j] = False


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())

    if n < 4:
        print("0")
    elif n == 4:
        print("1")
    else:
        count = 0
        for i in range(3, n // 2 + 1, 2):
            if (number[i] == True) and (number[n - i] == True):
                count += 1
        print(count)

---

풀이

• 이전에 풀었던 골드바흐의 추측 문제를 사용하여 위 문제를 해결했다.
• 에라토스테네스의 체를 사용하여 소수를 저장하는 리스트를 생성한다.
• 골드바흐의 추측 문제에서는 4보다 큰 짝수는 두 홀수 소수의 합으로 표현이 가능하다 했지만 위 문제에서는 2보다 큰 짝수는 두 소수의 합으로 표현이 가능하다고 한 두 문제의 차이를 이해해야 한다.
• 두 문제의 차이점은 4를 포함하는지의 유무로 4를 기준으로 하여 4보다 작은 경우, 4인 경우, 4보다 큰 경우로 나누어 문제를 해결한다.
• 4를 제외하면 짝수인 소수가 들어가는 경우가 없기 때문에 4보다 큰 짝수는 모두 홀수 소수의 합으로 나타낼 수 있다. 또한 순서만 다른 것은 같은 파티션으로 취급하기 때문에 입력받은 N의 1/2까지, 홀수만을 반복하도록하여 계산속도를 줄인다.