Cho n và k. Kiểm tra n có thể viết thành tổng của k số nguyên tố hay không.
Ví dụ: n=30, k=3 → True vì 30 = 2 + 11 + 17.
Giải thuật
- Nếu n < 2k: False (vì số nguyên tố nhỏ nhất là 2).
- Nếu k > 2: True (theo giả thuyết Goldbach yếu, mọi số lớn đủ có thể biểu diễn).
- Nếu k == 2:
- Nếu n chẵn: True (Goldbach).
- Nếu n-2 là nguyên tố: True.
- Ngược lại: False.
- Nếu k == 1: True nếu n là nguyên tố.
Ví dụ mã 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)) # Output: True
Đầu vào
30, 3
Đầu ra
True