หาจำนวนตัวประกอบคอมโพสิตสูงสุดของจำนวนใน Python

สมมติว่าเรามีจำนวน N (1 ≤ N ≤ 10^9) ต้องการแทน N เป็นผลรวมของตัวประกอบคอมโพสิต (จำนวนที่ไม่ใช่เฉพาะและมากกว่า 1) ให้ได้จำนวนตัวประกอบมากที่สุด คืนค่าจำนวนตัวประกอบสูงสุด หรือ -1 ถ้าไม่สามารถทำได้

เช่น N = 16 ผลลัพธ์คือ 4 เพราะ 16 = 4+4+4+4 (4 ตัวประกอบ) หรือ 8+8 (2 ตัวประกอบ) เลือกมากที่สุดคือ 4

ขั้นตอนการแก้ปัญหา (Dynamic Programming + Pattern)

1. คำนวณตาราง DP สำหรับค่าต่ำกว่า 16 (max_val) โดยใช้ตัวประกอบ 4, 6, 9
2. สำหรับ N ≥ 16 ใช้รูปแบบ: หยิบ 4 ไปเรื่อยๆ จนเหลือค่าน้อยกว่า 16 แล้วใช้ตาราง DP

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

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

อินพุต

16

เอาต์พุต

4