Tìm 4 ước số của N với tích lớn nhất và tổng bằng N - Python

Cho số N, tìm tất cả ước số của N và trả về tích của 4 ước số sao cho: Tổng 4 ước số bằng N. Tích 4 ước số là lớn nhất. Cả 4 ước số có thể bằng nhau để tối đa hóa tích.

Ví dụ: N = 60, kết quả là 50625 vì chọn 15 bốn lần (15+15+15+15=60, 15⁴=50625).

Thuật toán

1. Tìm tất cả ước số của N.
2. Sắp xếp danh sách ước số.
3. Duyệt qua tất cả tổ hợp 3 ước số (i, j, k), tính y = N - (i+j+k).
4. Nếu y > 0 và y là ước số của N, cập nhật tích lớn nhất.
5. In kết quả hoặc "Not possible".

Ví dụ code

from math import *
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)

Input

60

Output

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