使用 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 中的 i of(square root of n)，请执行

• 在 cand 的末尾插入 i

• 如果 n mod i 等于 0，则

• m := 糖果的大小

• 如果 k > 2*m 或 (k 与 2*m 相同且 n = (cand 的最后一个元素)^2)

• 返回-1

• 如果 k <= m，则

• 返回 can[k-1]

• 因子 := can[2*m - k]

• n/因子的返回商

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

示例

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