골드바흐의 추측을 이용해 정수 n을 k개의 소수 합으로 표현하기

25309번: K개의 소수 (acmicpc.net)

 

정수 n을 k개의 소수 합으로 표현하라는 문제

 

여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다.

 

그리고 문제는 n이 최대 $10^{8}$이고 k는 최대 10000이라 단순한 방법으로는 어렵다

 

먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다.

 

따라서 n < 2k이면 분해하는 것이 불가능하고, n >= 2k이면 일단 분해하는 것이 가능하다.

 

n,k = map(int,input().split())

if n < 2*k:
    
    print(-1)

 

 

만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다.

 

$O(\sqrt{n})$에 소수 판단할 수 있다.

 

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

 

 

다음 k = 2이면, n이 짝수인가 홀수인가에 따라 다르다.

 

여기서 골드바흐의 추측은 

 

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

 

증명되지는 않았지만 다행히 일반적으로 다루는 정수 범위 내에서는 참이다.

 

n >= 2k이고, k = 2일때 n이 짝수라면 골드바흐의 추측에 의해 가능하다.

 

이 경우 두 소수를 아무거나 찾아야한다.

 

def represent_two_prime(n):
    
    for i in range(2,n+1):
        
        if is_prime(i) and is_prime(n-i):
            
            return i

 

 

$O(N\sqrt{N})$처럼 보이긴 한데, 실제로 보면 n이 최대 $10^{8}$이면 최대 i = 1039정도에서 찾을 수 있다.

 

그러다보니까 아무거나 하나를 찾는다면 실제로는 $O(\sqrt{N})$정도 되는듯

 

이번에는 n >= 2k이고 k = 2에서 n이 홀수라면 이야기가 조금 다르다.

 

소수는 유일하게 2만 짝수이고, 나머지는 홀수라는 특징이 있다.

 

그런데, 짝수 + 짝수 = 짝수, 짝수 + 홀수 = 홀수, 홀수 + 홀수 = 짝수 라는 특징이 있다.

 

그러다보니 n이 홀수인데 2개의 소수 합으로 나타낼려면, 짝수 + 홀수로 나타낼수밖에 없는데, 

 

유일하게 2만 짝수이므로 2를 반드시 사용해야한다.

 

따라서, n - 2가 소수이면 2와 n-2의 합으로 나타낼 수 있고, n-2가 소수가 아니라면 분해하는 것이 불가능하다.

 

    elif k == 2:
        
        if n % 2 == 0:
            
            a = represent_two_prime(n)
            print(a,n-a)
        
        else:
            
            if is_prime(n-2):
                
                print(2,n-2)
            
            else:
                
                print(-1)

 

 

마지막으로 n >= 2k인데 k >= 3인경우는 반드시 k개의 소수 합으로 분해할 수 있다.

 

어떻게 가능한가?

 

n이 짝수라면 n - 2(k-2)도 짝수이다. 

 

왜냐하면 n = 2m이면 2m-2(k-2) = 2(m-(k-2))는 짝수니까

 

그러므로 2를 먼저 k-2번 더하고 나서, 나머지 2개는 n-2(k-2)는 짝수이므로, 이를 골드바흐의 추측에 따라 2개의 소수 합으로 분해하면 된다.

 

n이 홀수라면 n - 3 - 2(k-3)도 짝수이다.

 

n = 2m+1이면 2m-2 - 2(k-3) = 2(m-1-(k-3))이므로 짝수

 

그러므로 2를 먼저 k-3번 더하고 나서 나머지 3개중 1개는 3을 사용하고 남은 2개는 n-3-2(k-3)이 짝수니까

 

골드바흐의 추측에 따라 2개의 소수 합으로 분해하면 된다

 

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

def represent_two_prime(n):
    
    for i in range(2,n+1):
        
        if is_prime(i) and is_prime(n-i):
            
            return i

n,k = map(int,input().split())

#가장 작은 소수는 2이므로, k개의 소수로 만들 수 있는 가장 작은 정수는 2k
if n < 2*k:
    
    print(-1)

else:
    
    #n을 1개의 소수로 만들 수 있는가?
    #n 자체가 소수인지 아닌지 판단
    if k == 1:
        
        if is_prime(n):
            
            print(n)
        
        else:
            
            print(-1)
    
    #2개의 소수로 만들 수 있는가?
    elif k == 2:
        
        #n이 짝수이면 2보다 큰 모든 짝수는 2개의 소수 합으로 분해할 수 있다
        if n % 2 == 0:
            
            a = represent_two_prime(n)
            print(a,n-a) #아무거나 빠르게 하나를 찾는다
        
        else:
            
            #n이 홀수라면, 짝수 + 홀수 = 홀수이고 소수중 2만이 유일하게 짝수이므로
            #2를 반드시 사용해야하고, 나머지 n-2가 소수인지 아닌지 판단
            if is_prime(n-2):
                
                print(2,n-2)
            
            else:
                
                print(-1)
        
    else: #n을 3개 이상의 소수로 만들 수 있는가?
        
        if n % 2 == 0:
            
            #n이 짝수이면 n - 2(k-2)도 짝수이다.
            #따라서 2를 k-2번 사용하고, 나머지 2개는 n-2(k-2)를 2개의 소수 합으로 분해
            for _ in range(k-2):
                
                print(2,end=' ')
            
            a = represent_two_prime(n-2*(k-2))
            print(a,end=' ')
            print(n-2*(k-2)-a,end=' ')
        
        else:
            
            #n이 홀수이면 n-3-2(k-3)도 짝수이다.
            #따라서 2를 k-3번 사용, 3을 1번 사용, 나머지 2개는 n-3-2(k-3)을 2개의 소수 합으로 분해
            for _ in range(k-3):
                
                print(2,end=' ')
            
            print(3,end=' ')
            a = represent_two_prime(n-3-2*(k-3))
            print(a,end=' ')
            print(n-3-2*(k-3)-a,end=' ')