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

Giả sử chúng ta có hai giá trị dương n và k. Bây giờ coi như chúng ta có một danh sách tất cả các thừa số của n được sắp xếp theo thứ tự tăng dần, chúng ta phải tìm thừa số thứ k trong danh sách này. Nếu có ít hơn k thừa số, thì trả về -1.

Vì vậy, nếu đầu vào là n =28 k =4, thì đầu ra sẽ là 7 bởi vì, thừa số của 28 là [1,2,4,7,14,28], phần tư là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu k giống với 1 thì

  • trả lại 1

• cand:=danh sách có một phần tử [1]

• đối với tôi trong phạm vi từ 2 đến 1 + tầng của (căn bậc hai của n), thực hiện

  • nếu n mod tôi giống 0 thì

    • chèn tôi vào cuối cand

  • m:=kích thước của cand

• nếu k> 2 * m hoặc (k giống với 2 * m và n =(phần tử cuối cùng của cand) ^ 2)

  • trả về -1

• nếu k <=m, thì

  • trả về cand [k-1]

• hệ số:=cand [2 * m - k]

• trả về thương số của n / hệ số

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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