โปรแกรมตรวจสอบว่า n แสดงเป็นผลรวมของ k จำนวนเฉพาะได้หรือไม่ใน Python

ได้รับ n และ k ต้องการตรวจสอบว่า n สามารถเขียนเป็นผลรวมของ k จำนวนเฉพาะได้หรือไม่

ตัวอย่าง: n=30, k=3 → True เพราะ 30 = 2 + 11 + 17

ขั้นตอนการแก้ปัญหา

1. หาก n < 2k → False (เพราะจำนวนเฉพาะน้อยที่สุดคือ 2)
2. หาก k > 2 → True (ทฤษฎี Goldbach แบบอ่อน)
3. หาก k = 2:
   • n คู่ → True (Goldbach conjecture)
   • n คี่ → ตรวจสอบว่า n-2 เป็นจำนวนเฉพาะหรือไม่
4. หาก k = 1 → ตรวจสอบว่า n เป็นจำนวนเฉพาะหรือไม่

ตัวอย่างโค้ด Python

def isPrime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def solve(n, k):
    if n < 2 * k:
        return False
    if k > 2:
        return True
    if k == 2:
        if n % 2 == 0:
            return True
        return isPrime(n - 2)
    return isPrime(n)

# ทดสอบ
n = 30
k = 3
print(solve(n, k))  # ผลลัพธ์: True

อินพุตตัวอย่าง

30, 3

เอาต์พุตตัวอย่าง

True