[알고리즘] 골드바흐의 추측

문제

골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다. 이때 하나의 소수를 두 번 사용하는 것은 허용한다. - 위키백과

위 설명에서 2보다 큰 모든 짝수를 두 소수의 합으로 나타낸 것을 골드바흐 파티션이라고 합니다.

예)
100 == 47 + 53
56 == 19 + 37

2보다 큰 짝수 n이 주어졌을 때, 골드바흐 파티션을 출력하는 코드를 작성하세요.

개념

1. n이 주어졌을 때 n까지의 모든 소수 출력
2. (n - 출력된 소수)가 소수인지 확인
3. 오름차순 정렬
4. 중복제거
   예를들어 n = 100 이면 [47, 53], [53, 47]은 중복됨

코드

import math

def goldbach(n):
    if n <= 2 or n % 2 != 0:
        return '적절하지 못한 입력(2보다 큰 짝수)'
    
    def prime(n):
        array = [True for i in range(n+1)]
        # 에라토스테네스의 체
        for i in range(2, int(math.sqrt(n)) + 1):
            if array[i] == True:
                j = 2
                while i * j <= n:
                    array[i * j] = False
                    j += 1
        return [ i for i in range(2, n+1) if array[i] ]

    result = []

    prime_arr = prime(n) # n까지 전체 소수 리스트
    for i in prime_arr:
        if (n - i) in prime_arr: # n-소수가 소수인지 판별
            values = sorted([i, n-i])
            if values in result: # 중복 제거
                return result
            result.append(values)

    return result

if __name__ == '__main__':

    print(goldbach(100))
    # [[3, 97], [11, 89], [17, 83], [29, 71], [41, 59], [47, 53]]
    print(goldbach(56))
    # [[3, 53], [13, 43], [19, 37]]