使用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

更新于：2021年5月29日

536 次浏览

开始您的职业生涯

完成课程获得认证

开始
广告