골드바흐의 추측을 알고리즘 문제에 적용하는 방법

1. 문제

 

1153번: 네 개의 소수 (acmicpc.net)

1153번: 네 개의 소수

 

임의의 자연수가 소수 4개의 합으로 분해될 수 있는지 구하는 문제

 

2. 풀이

 

어떻게 푸는지 모르겠다면.. 브루트 포스로 접근해보는게 가장 현명하다

 

n이 주어질때 n을 4개의 소수의 합으로 분해하고 싶다면, n보다 작은 소수들로만 분해할 수 있을 것이다

 

n보다 작은 소수의 리스트를 에라토스테네스의 체로 구하고 

 

이 체에서 4중 for문으로 4개를 선택해서 더해보고 n이 되는지 검사해서 찾기만 하면 바로 break해서 탈출하고 

 

출력해준다

 

from sys import stdin

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int((n+1)**(1/2))+1):
        
        for j in range(i+i,n+1,i):
            
            if result[i] == 1:
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

n = int(stdin.readline())

prime_list = get_prime(n)

p = len(prime_list)

find = False

for a in range(p):
    
    for b in range(a,p):
        
        for c in range(b,p):
            
            for d in range(c,p):
                
                if prime_list[a]+prime_list[b]+prime_list[c]+prime_list[d] == n:
                    
                    find = True
                    break
            
            if find:
                
                break
        
        if find:
            
            break
    
    if find:
        
        break

if find == False:
    
    print(-1)

else:

    answer = [prime_list[a],prime_list[b],prime_list[c],prime_list[d]]

    answer.sort()

    print(*answer)

 

근데 이러면.. 통과는 했지만 pypy로 7초나 걸린다.. 시간제한은 2초인데

 

 

3. 골드바흐의 추측

 

"2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다"

 

"5보다 큰 모든 홀수는 세 소수의 합으로 나타낼 수 있다"

 

 

첫번째 명제가 참이면, 두번째 명제는 참이다. 

 

왜냐하면 5보다 큰 모든 홀수는 2보다 큰 어떤 짝수와 3의 합이기 때문이다. 

 

그래서 첫번째 명제를 "골드바흐의 강한 추측"

 

두번째 명제를 "골드바흐의 약한 추측"이라고 부른다

 

 

4. 골드바흐의 약한 추측의 증명

 

1937년 어떤 러시아의 수학자는 계산을 하기에 충분히 효율적인 수 이상의 홀수는 3개의 홀수 소수의 합으로 표현할 수 있음을 증명했다.

 

2013년, H. A. Helfgott라는 수학자가 "계산을 하기에 충분히 효율적인 수"를 $10^{30}$까지 될 수 있다는 것을 보였다.

 

그리고 그 밑의 수에 대해서는 동료 수학자가 브루트 포스로 3개의 소수의 합으로 표현할 수 있다는 것을 보일 수 있었다.

 

그래서 2013년 "5보다 큰 모든 홀수에 대해 3개의 소수 합으로 표현할 수 있다"는 골드바흐의 약한 추측을 증명하였다.

 

 

5. 골드바흐의 강한 추측의 증명 시도

 

"4이상 모든 짝수는 두 소수의 합으로 나타낼 수 있다"를 IBM에서 컴퓨터로 찾아보았는데 400경까지 검사해봤더니 성립하지 않는 수를 찾을 수 없었다고 한다

 

 

6. 응용

 

(골드바흐의 추측이 정말 참이라면... 그래도 400경까지는 참이니까) "8이상의 모든 수는 4개의 소수의 합으로 표현"할 수 있다

 

왜 그런지 생각해보자.

 

8이상의 N = a + b + c + d라고 할 때

 

N이 짝수라면, N - 4도 짝수이므로 골드바흐의 추측에 의해 짝수인 N-4는 2개의 소수의 합으로 표현할 수 있다.

 

N - 4 = a + b

 

따라서 N = a + b + 2 + 2인 4개의 소수로 표현할 수 있다.

 

 

N이 홀수라면 N - 5는 짝수이다. 

 

N = 2k+1이면, N-5 = 2k-4이므로 짝수이다.

 

그러므로 골드바흐의 추측에 의해 짝수인 N-5는 2개의 소수의 합으로 표현할 수 있다.

 

N - 5 = a + b

 

따라서 N = a + b + 2 + 3으로 4개의 소수의 합으로 표현할 수 있다.

 

 

따라서 입력받은 수가 짝수이면 2개의 소수 2,2는 이미 찾았고 나머지 2개만 찾으면 된다.

 

마찬가지로 홀수이면 2개의 소수 2,3은 찾았고 나머지 2개만 찾으면 되겠다.

 

나머지 2개는 2중 for문으로 찾아보면 4중 for문보다는 시간복잡도에서 효율적이겠지..

 

from sys import stdin

def get_prime(n):
    
    result = [1]*(n)

    for i in range(2,int((n)**(1/2))+1):
        
        for j in range(i+i,n,i):
            
            if result[i] == 1:
                
                result[j] = 0
    
    return [i for i in range(2,n) if result[i] == 1]

n = int(stdin.readline())

if n < 8:
    
    print(-1)

else:

    if n % 2 == 0:
        
        n -= 4

        answer = [2,2]
    
    else:
        
        n -= 5

        answer = [2,3]

    prime_list = get_prime(n)

    p = len(prime_list)

    find = False

    for a in range(p):
        
        for b in range(a,p):

            if prime_list[a] + prime_list[b] == n:

                find = True

                answer.append(prime_list[a])
                answer.append(prime_list[b])

                break

        if find:

            break
    
    if find:
        
        print(*answer)
    
    else:
        
        print(-1)

 

 

이러면 python3로 0.4초 정도 걸린다 

 

시간복잡도가 훨씬 개선되었다

 

 

7. 최적화

 

더 빠르게 푸신분의 풀이를 참고해서 분석해보자

 

에라토스테네스의 체를 쓰는게 오히려 비효율적이다

 

위에서 응용한대로 골드바흐의 추측에 의해 n이 8보다 작으면 4개의 소수 합으로 표현할 수는 없고

 

n이 8이상일때, n이 짝수이면 n-4도 짝수이고, n이 홀수이면 n-5는 짝수이다

 

그러면 n-4와 n-5는 짝수이므로 이 수에 대해 두 소수의 합으로 표현할 수 있는 어떤 두 소수를 찾기만 하면 된다

 

 

n-4나 n-5를 m이라고 해보면.. m은 짝수이므로 2로 나눌 수 있다

 

k = m/2라고 한다면.. 투포인터 개념으로 한쪽은 작아지는 방향 k-i, 한쪽은 커지는 방향 k+i를 검사한다.

 

k-i와 k+i가 각각 소수라면.. 두 소수의 합 k-i + k+i = 2k = m 이므로 원하는 두 소수 k-i, k+i를 찾는다

 

i = 0부터 k-1까지 순회해서 k-i와 k+i에 대해 소수 판정을 해서 전부 소수이면 바로 return

 

def is_prime(n):
    
    if n == 1:
        
        return False
    
    else:
        
        for i in range(2,int(n**(1/2))+1):
            
            if n % i == 0:
                
                return False
        
        return True

def goldbach(m):
    
    k = m//2

    for i in range(k):
        
        if is_prime(k-i) and is_prime(k+i):
            
            return [k-i,k+i]

 

그리고 위에서 한 대로 n이 8보다 작으면 -1을 출력하고

 

n이 8이상인데 짝수이면 2,2는 빼놓고 n-4에 대해 두 소수의 합을 찾고

 

홀수이면 2,3은 빼놓고 n-5에 대해 두 소수의 합을 찾는다

 

n = int(input())

if n < 8:
    
    print(-1)

else:
    
    if n % 2 == 0:
        
        n -= 4

        answer = goldbach(n)

        answer.append(2)
        answer.append(2)

    
    else:
        
        n -= 5

        answer = goldbach(n)

        answer.append(2)
        answer.append(3)
    
    print(*answer)

 

이러면 0.04초만에 해결 가능

 

참조

 

 

골드바흐의 추측, ‘약하게’ 증명됐다! : 동아사이언스 (dongascience.com)

골드바흐의 추측, ‘약하게’ 증명됐다!

 

 

골드바흐 추측 - 나무위키 (namu.wiki)

골드바흐 추측 - 나무위키