หา 4 ตัวประกอบของ N ที่ให้ผลคูณมากที่สุดและผลรวมเท่ากับ N (Python)

โจทย์: หาตัวประกอบ 4 ตัวของ N ที่ผลรวมเท่ากับ N และผลคูณมากที่สุด สามารถเลือกตัวประกอบซ้ำกันได้

ตัวอย่าง: N = 60 → ตัวประกอบคือ 1,2,3,4,5,6,10,12,15,20,30,60 → เลือก 15 สี่ครั้ง → ผลคูณ = 50625

อัลกอริทึม

1. หาตัวประกอบทั้งหมดของ N (วนลูป 1 ถึง √N)
2. เรียงตัวประกอบจากน้อยไปมาก
3. วนลูป 3 ชั้น (i, j, k) หาตัวประกอบ 3 ตัวแรก
4. คำนวณตัวที่ 4: y = N - factors[i] - factors[j] - factors[k]
5. ถ้า y เป็นตัวประกอบของ N (N % y == 0) → คำนวณผลคูณ และเก็บค่าสูงสุด

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

from math import sqrt

def get_factors(n):
    factors = []
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            factors.append(i)
            factors.append(n // i)
    factors.sort()
    print("Factors are:", factors)

    final_prod = 1
    flag = 1
    for i in range(len(factors)):
        for j in range(i, len(factors)):
            for k in range(j, len(factors)):
                y = n - factors[i] - factors[j] - factors[k]
                if y <= 0:
                    break
                if n % y == 0:
                    flag = 0
                    final_prod = max(factors[i] * factors[j] * factors[k] * y, final_prod)
    if flag == 0:
        print("Product is", final_prod)
    else:
        print("Not possible")

n = 60
get_factors(n)

ผลลัพธ์

Factors are [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
Product is 50625

ความซับซ้อน: O(d³) โดย d = จำนวนตัวประกอบ (ปกติไม่มาก) ใช้ได้กับ N ที่ไม่ใหญ่เกินไป