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

Cho số N, tìm 4 ước số của N có tổng bằng N và tích lớn nhất. Các ước số có thể trùng nhau.

Ví dụ: N=60 → Ước: 1,2,3,4,5,6,10,12,15,20,30,60 → Chọn 15,15,15,15 → Tích=50625.

Thuật toán tối ưu O(d²) với d = số ước

1. Tìm tất cả ước số của N lưu vào list v.
2. Tính tất cả tổng cặp ước v[i] + v[j] < N, lưu vào v1 và map map1[sum] = (v[i], v[j]).
3. Với mỗi tổng s trong v1, kiểm tra N - s có trong map không. Nếu có, lấy 4 ước số tương ứng, tính tích, cập nhật max.

Ví dụ code

from math import sqrt, ceil, floor

def get_product(n):
    my_map = {}
    v = []
    v1 = []
    for i in range(1, ceil(sqrt(n)) + 1):
        if n % i == 0:
            v.append(i)
            if i != n // i and i != 1:
                v.append(n // i)
    s = len(v)
    maximum = -1
    map1 = [0] * (n + 5)
    for i in range(s):
        for j in range(i, s):
            if v[i] + v[j] < n:
                v1.append(v[i] + v[j])
                map1[v[i] + v[j]] = [v[i], v[j]]
                my_map[v[i] + v[j]] = 1
    s = len(v1)
    for i in range(s):
        element = n - v1[i]
        if element in my_map:
            a, b = map1[v1[i]]
            c, d = map1[element]
            maximum = max(a * b * c * d, maximum)
    if maximum == -1:
        print("Not Possible")
    else:
        print("Maximum product", maximum)

n = 60
get_product(n)

Input

60

Output

Maximum product 50625