Chương trình Python tìm ước số 'tốt nhất' của một số

Cho số n. Tìm ước số của n "tốt nhất" theo tiêu chí:

1. Ước số có tổng chữ số lớn nhất.
2. Nếu bằng nhau về tổng chữ số, chọn ước số nhỏ hơn.

Ví dụ: n = 180 → ước số là [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]. Tổng chữ số max = 9 (tại 9, 18, 36, 45, 90, 180). Chọn 9 vì nhỏ nhất.

Thuật toán

• Duyệt i từ 2 đến n.
• Nếu i chia hết n, tính tổng chữ số của i.
• Cập nhật ước tốt nhất khi tổng chữ số lớn hơn (không cần xử lý tie-break vì duyệt tăng dần).

Ví dụ mã nguồn

def solve(n):
    div = 1
    md = 1
    for i in range(2, n + 1):
        if n % i > 0:
            continue
        k = i
        s = 0
        while k > 0:
            s += k % 10
            k //= 10
        if s > md:
            md = s
            div = i
    return div

n = 180
print(solve(n))  # 9

Đầu vào / Đầu ra

Input:  180
Output: 9