Chương trình tìm ước số thứ k của n bằng Python

Cho hai số nguyên dương n và k. Liệt kê tất cả ước số của n theo thứ tự tăng dần, tìm ước số thứ k. Nếu ít hơn k ước số, trả về -1.

Ví dụ: n = 28, k = 4. Ước số của 28: [1,2,4,7,14,28]. Thứ 4 là 7.

Thuật toán giải quyết (Tối ưu O(√n))

• Nếu k == 1: trả về 1.
• Thu thập các ước số nhỏ (≤ √n) vào danh sách cand.
• m := len(cand). Tổng số ước số là 2m (nếu n không phải bình phương hoàn hảo) hoặc 2m-1 (nếu n là bình phương).
• Nếu k > 2m hoặc (k == 2m và n == cand[-1]^2): trả về -1.
• Nếu k ≤ m: trả về cand[k-1] (ước nhỏ).
• Ngược lại: ước lớn thứ (k-m) tương ứng với cand[2m-k], trả về n // cand[2m-k].

Ví dụ triển khai

from math import floor

def solve(n, k):
    if k == 1:
        return 1
    cand = [1]
    for i in range(2, 1 + floor(pow(n, 0.5))):
        if n % i == 0:
            cand.append(i)
    m = len(cand)
    if k > 2*m or (k == 2*m and n == cand[-1]**2):
        return -1
    if k <= m:
        return cand[k-1]
    factor = cand[2*m - k]
    return n // factor

n = 28
k = 4
print(solve(n, k))

Đầu vào

28, 4

Đầu ra

7