Tìm số lượng thành phần hợp số lớn nhất của một số trong Python

Cho số N (1 ≤ N ≤ 10^9). Phân tích N thành tổng của nhiều số hợp số (composite) nhất có thể. Trả về số lượng thành phần lớn nhất, hoặc -1 nếu không phân tích được.

Ví dụ: 16 = 4+4+4+4 (4 thành phần) hoặc 8+8 (2 thành phần) → kết quả 4.

Giải thuật

Quan sát: số hợp số nhỏ nhất là 4. Để tối đa số thành phần, nên dùng nhiều 4 nhất có thể.

• Tiền tính bảng DP cho N < 16 (max_val = 16).
• Với N ≥ 16: lấy t = (N - 16) // 4 + 1, kết quả = t + table[N - 4*t].
• Cơ sở: dùng các số hợp số 4, 6, 9 để xây dựng bảng DP.

Ví dụ

max_val = 16

def pre_calc():
    table = [-1] * max_val
    table[0] = 0
    v = [4, 6, 9]
    for i in range(1, max_val):
        for k in range(3):
            j = v[k]
            if i >= j and table[i - j] != -1:
                table[i] = max(table[i], table[i - j] + 1)
    return table

def max_summ(table, n):
    if n < max_val:
        return table[n]
    else:
        t = int((n - max_val) / 4) + 1
        return t + table[n - 4 * t]

n = 16
table = pre_calc()
print(max_summ(table, n))

Đầu vào

16

Đầu ra

4