使用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 + n平方根的向下取整的范围内的i，执行以下操作 –
- 如果n模i与0相同，则
  - 在cand的末尾插入i
- m：cand的大小
如果k> 2 * m或（k与2 * m相同且n = cand的最后一个元素的平方）
- 返回-1
如果k≤m，则
- 返回cand [k-1]
因子：cand [2m – k]
返回n / factor的商

让我们看一下以下实现以获得更好的理解-

更多Python相关文章，请阅读：Python 教程

示例

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