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

두 개의 입력값 n과 k가 주어졌을 때, n이 정확히 k개의 소수의 합으로 표현될 수 있는지 판별하는 문제입니다.

예를 들어 n = 30, k = 3이 입력으로 주어진다면, 30은 2 + 11 + 17처럼 세 개의 소수의 합으로 나타낼 수 있으므로 결과는 True가 됩니다.

문제 해결 접근 방식

이 문제는 다음과 같은 논리적 단계를 통해 효율적으로 해결할 수 있습니다.

• n < 2k인 경우: 가장 작은 소수는 2이므로, k개의 소수의 합으로 만들 수 있는 최솟값은 2k입니다. 따라서 n이 2k보다 작으면 표현이 불가능하며 False를 반환합니다.
• k > 2인 경우: 골드바흐 추측에 따르면 충분히 큰 짝수는 두 소수의 합으로 표현할 수 있고, 여기에 2를 추가하는 방식으로 조합을 확장할 수 있으므로 True를 반환합니다.
• k = 2인 경우:
  • n이 짝수라면 골드바흐 추측에 의해 두 소수의 합으로 표현 가능하므로 True를 반환합니다.
  • n이 홀수라면 두 소수 중 하나는 반드시 2(유일한 짝수 소수)여야 하므로, (n − 2)가 소수인지 검사합니다. 소수라면 True, 아니면 False를 반환합니다.
• k = 1인 경우: n 자체가 소수인지 검사하여 소수라면 True, 아니면 False를 반환합니다.

구현 예제

다음은 위 로직을 파이썬으로 구현한 코드입니다.

def check_prime(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 check_prime(n-2):
            return True
        return False
    if check_prime(n):
        return True
    return False

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

입력

30, 3

출력

True

위 코드에서 check_prime() 함수는 2부터 num−1까지의 수로 나누어 떨어지는지 확인하는 방식으로 소수 여부를 판별합니다. 이후 solve() 함수가 앞서 설명한 조건 분기를 순서대로 적용하여 최종 결과를 반환합니다.