[python] boj 17103 골드바흐 파티션

알고리즘은 꾸준히 풀었는데 글 업로드를 안 했다...정말이다..정말 열심히 풀었다..

 

어쨌든 낮은 난이도에 비해 배울 점이 많은 문제라서 이렇게 기록을 남기게 되었다.

 

www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

기본 아이디어

• 두 소수의 합으로 짝수를 이루는 과정에서 각 수에 대해 소수이지 확인하는 절차가 필요하다.
• 입력이 첫째줄에 테스트 케이스의 수가 주어지고 그 수 만큼 테스트 케이스가 주어지는 구조이다.
• 각 수에 대해 소수인지 체크한 리스트를 한 번만 만들어놓으면 여러 테스트 케이스에서 공용으로 사용할 수 있다.
• 소수인지 확인하는 과정에서도 에라토스테네스의 체를 활용한다. 참고) wikidocs.net/21638

위키독스

• 2보다 큰 짝수 num은 num = i + (num - i) 로 나타낼 수 있고 i랑 (num - i)가 둘 다 소수인지만 증명하면 골드바흐의 추측에 해당한다.

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)

유의사항

• 여러 테스트 케이스가 주어지는 경우 공용으로 사용할만한 코드가 있다면 반복문 바깥으로 빼서 활용하면 시간을 많이 줄일 수 있다.
• 소수를 구하는 로직이 필요하다면 에라토스테네스를 활용하자.