পাইথনে n কি k প্রাইম সংখ্যার যোগফল হিসেবে প্রকাশ করা সম্ভব কিনা চেক করার প্রোগ্রাম

দুই ইনপুট n এবং k দেওয়া আছে। n কি kটি প্রাইম সংখ্যার যোগফল হিসেবে লেখা সম্ভব কিনা চেক করুন।

উদাহরণ

n = 30, k = 3 → আউটপুট: True

30 = 2 + 11 + 17

এলগরিদম (গোল্ডব্যাকের অনুমান ভিত্তিক)

1. যদি n < 2k: False (প্রতিটি প্রাইম ≥ ২)
2. যদি k > 2: True (সদা সম্ভব)
3. যদি k == 2:
   • n জোড় হলে: True
   • n-2 প্রাইম হলে: True
   • অন্যথায়: False
4. যদি 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))  # আউটপুট: True

ইনপুট / আউটপুট

30, 3
True