使用Python查詢n的第k個因子的程式

假設我們有兩個正值n和k。現在考慮我們有一個按升序排列的n的所有因子的列表，我們必須找到此列表中的第k個因子。如果因子少於k個，則返回-1。

因此，如果輸入類似於n = 28 k = 4，則輸出將為7，因為28的因子為[1,2,4,7,14,28]，第四個是7。

為了解決這個問題，我們將遵循以下步驟：

• 如果k等於1，則

  • 返回1

• cand := 一個包含一個元素[1]的列表

• 對於範圍從2到1 + floor(n的平方根)的i，執行：

  • 如果n mod i等於0，則

    • 將i插入cand的末尾

  • m := cand的大小

• 如果k > 2*m 或 (k等於2*m 且 n = (cand的最後一個元素)^2)

  • 返回-1

• 如果k <= m，則

  • 返回cand[k-1]

• factor := cand[2*m - k]

• 返回n/factor的商

讓我們看看下面的實現，以便更好地理解：

示例

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))

輸入

28, 4

輸出

7

Arnab Chakraborty

更新於：2021年5月29日

536 次瀏覽

開始您的職業生涯

完成課程獲得認證

開始