पायथन में जांचना कि n को k प्राइम के योग के रूप में दर्शाया जा सकता है या नहीं

मान लीजिए हमारे पास दो इनपुट n और k हैं। हमें जांचना है कि क्या n को k संख्या के प्राइम मानों के योग के रूप में दर्शाया जा सकता है या नहीं।

उदाहरण के लिए, यदि इनपुट है n = 30, k = 3, तो आउटपुट होगा True क्योंकि 30 को 2 + 11 + 17 की तरह दर्शाया जा सकता है।

समाधान दृष्टिकोण

यह संख्या सिद्धांत पर आधारित है (गोल्डबैक की कमजोर परिकल्पना)। मुख्य अंतर्दृष्टि:

• यदि n < 2k, असंभव (सबसे छोटा प्राइम 2 है)।
• यदि k > 2, हमेशा संभव (गोल्डबैक की कमजोर परिकल्पना)।
• यदि k == 2: यदि n सम है तो True, अन्यथा जांचें कि n-2 प्राइम है या नहीं।
• यदि k == 1: जांचें कि n प्राइम है या नहीं।

पायथन कार्यान्वयन

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