Chương trình kiểm tra số n có biểu diễn thành tổng k số nguyên tố không trong Python

Cho n và k. Kiểm tra xem n có thể viết thành tổng của đúng k số nguyên tố hay không.

Ví dụ: n = 30, k = 3 → True vì 30 = 2 + 11 + 17.

Thuật toán giải quyết (Dựa trên định lý Goldbach)

1. Nếu n < 2k: False (tổng k số nguyên tố nhỏ nhất là 2k)
2. Nếu 2: True (luôn biểu diễn được - định lý Goldbach yếu)
3. Nếu k == 2:
   • Nếu n chẵn: True (Goldbach mạnh)
   • Nếu n-2 nguyên tố: True (2 + (n-2))
   • Ngược lại: False
4. Nếu k == 1: trả về True nếu n nguyên tố

Ví dụ minh họa

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))

Đầu vào

30, 3

Đầu ra

True