Python으로 n이 k개의 소수의 합으로 표현 가능한지 확인하는 프로그램

문제 설명

두 개의 숫자 n과 k가 주어졌을 때, n이 정확히 k개의 소수(素數)의 합으로 표현될 수 있는지 판별하는 프로그램을 만들어 보겠습니다.

예를 들어 입력이 n = 30, k = 3이라면 결과는 True입니다. 30을 2 + 11 + 17처럼 세 개의 소수의 합으로 나타낼 수 있기 때문입니다.

해결 전략

이 문제는 경우를 나누어 다음과 같이 접근할 수 있습니다.

1. n < 2k인 경우: 소수 중 가장 작은 값은 2이므로, k개의 소수의 합은 최소 2k입니다. 따라서 n이 2k보다 작으면 표현이 불가능하며 False를 반환합니다.
2. k > 2인 경우: n ≥ 2k이기만 하면 항상 k개의 소수의 합으로 표현할 수 있으므로 True를 반환합니다.
3. k = 2인 경우:
   • n이 짝수라면 골드바흐 추측(Goldbach conjecture)에 따라 두 소수의 합으로 표현할 수 있습니다. 이 추측은 아직 완전히 증명되지 않았지만 매우 넓은 범위까지 검증되어 있으므로 True를 반환합니다.
   • n이 홀수라면 두 소수 중 하나는 반드시 2여야 합니다. 따라서 (n − 2)가 소수인지 검사하고, 소수이면 True, 아니면 False를 반환합니다.
4. k = 1인 경우: n 자체가 소수인지 검사하여 그 결과를 반환합니다.

Python 구현 예제

다음 코드를 통해 위 로직을 직접 확인해 보겠습니다.

def isPrime(num):
   if num > 1:
      for i in range(2, num):
         if num % i == 0:
            return False
      return True
   return False

def solve(n, k):
   if n < k*2:
      return False
  
   if k > 2:
      return True

   if k == 2:
      if n%2 == 0:
         return True

      if isPrime(n-2):
         return True
      return False

   if isPrime(n):
      return True
   return False

n = 30
k = 3
print(solve(n, k))

코드 설명

isPrime() 함수는 2부터 num − 1까지의 수로 차례대로 나누어 떨어지는지 확인하는 방식으로 소수 여부를 판별합니다. 성능을 개선하려면 √num까지만 검사하도록 최적화할 수 있습니다.

solve() 함수는 앞서 설명한 경우의 수 로직을 그대로 구현하여, n이 k개의 소수의 합으로 표현 가능한지 여부를 불리언 값으로 반환합니다.

실행 결과

입력

30, 3

출력

True