백준: 17103 골드바흐 파티션

문제

17103번: 골드바흐 파티션

 

문제 풀이

 골드바흐의 추측은 두 소수의 차가 가장 큰 것을 반환하는 것이므로 최초에 만족하는 소수를 찾은 경우 더 이상 진행하지 않고 중지하면 된다. 이와 달리 골드 바흐 파티션은 순서가 다른 소수 예를 들어 6인 경우 (1, 5) (5, 1)은 동일하게 취급하고 짝수가 주어 질 때 만족하는 개수를 반환하는 문제이다.

 

from sys import stdin


def is_prime(n):
    nums = [True] * n
    for i in range(2, int(n ** 0.5) + 1):
        if nums[i]:
            for j in range(i + i, n, i):
                nums[j] = False
    return nums


if __name__ == "__main__":
    T = int(stdin.readline())
    nums = is_prime(1000000)
    for _ in range(T):
        n = int(stdin.readline())
        cnt = 0
        for i in range(3, n // 2 + 1, 2):
            if nums[i] and nums[n - i]:
                cnt += 1
        print(cnt)

 골드바흐 추측과 유사한 코드로 카운트만 하도록 추가하였는데 아무리 수정하고 잘못된 부분을 찾아도 채점하다가 결국엔 틀렸다고 한다. 어디가 문제인지 계속 고민해 보아도 잘 모르겠다.😥

 

 그래도 삽질하고 방법을 계속 고민하면서 에스토스테네스의 체를 조금 더 명확히 이해할 수 있는 기회가 된 것 같다.