골드바흐 파티션 풀이

문제 링크: https://www.acmicpc.net/problem/17103

백준 알고리즘 기초 1/2 301에서 6번째 - 17103번 골드바흐 파티션을 풀어보았다.

 

풀이: 골드바흐 파티션의 수를 구하는 문제이다.

파이썬의 경우, 기존의 에라토스테네스의 체를 이용하는 코드는 하도 시간초과가 나서 https://week-year.tistory.com/171 이 코드를 사용했다.

 

C++

 

Python

def get_primary_list(n):
    array = [1 for _ in range(n+1)]

    for i in range(2, int(n ** 0.5) + 1):
        if array[i]:
            j = 2

        while i * j <= n:
            array[i * j] = 0
            j += 1

    return array

T = int(input())
nums = [int(input()) for _ in range(T)]
max_num = max(nums)
primarys = get_primary_list(max_num)

for num in nums:
    result = 0

    for i in range(2, num // 2 + 1):
        if primarys[i] and primarys[num - i]:
            result += 1

    print(result)

Java