时间戳

首页 > 解决方案 > 当我知道 n 的平方根的所有因数时，如何得到数 n 的所有因数？

python - 当我知道 n 的平方根的所有因数时，如何得到数 n 的所有因数？

问题描述

我有一个算法，它返回所有因素的列表，n但只检查sqrt(n). 但是，我知道可以n仅使用 的因子列表来获得因子sqrt(n)。

功能：

def get_factors(n):
    sqrtn = floor(sqrt(n))
    factors = []

    factors.append(1)
    for factor in range(2, sqrtn):
        if n % factor == 0:
            factors.append(factor)
    factors.append(sqrtn)
    
    return factors

上面的代码返回[1, 2, 4, 5, 10]的输入n=100，但我需要操作函数调用后返回的列表并使其[1, 2, 4, 5, 10, 20, 25, 50, 100]（的所有因素n）。我只有一个模糊的概念，即函数返回的列表只是整个因子列表的左半部分。我将如何以编程方式处理这个问题？

标签： python

解决方案

我认为你正在寻找这个：

start = -2 if n // factors[-1] == factors[-1] else -1
factors.extend(n // f for f in factors[start::-1])

对于任何一对数字n = a * b，其中一个a, b必须小于或等于sqrt(n)，一个必须大于或等于它。重新排列定义给出a = n // b，其中//是 Python 的地板除法运算符，它保证您的结果保持为整数。

请注意，我建议向后迭代列表。在您的情况下，这有两个优点：

  1. 随着第一个因素的减少，第二个因素增加，以升序为您提供列表的后半部分。
  2. 在迭代期间修改列表是不明智的。这适用于显式循环或我传递给extend这里的惰性迭代器。获取列表的一部分有效地制作副本，因此您不再就地修改。

对于您的具体示例：

>>> factors = [1, 2, 4, 5, 10]
>>> n = 100
>>> start = -2 if n // factors[-1] == factors[-1] else -1
>>> factors.extend(n // f for f in factors[start::-1])
>>> factors
[1, 2, 4, 5, 10, 20, 25, 50, 100]

还有一个：

>>> factors = [1, 5, 13]
>>> n = 325
>>> start = -2 if n // factors[-1] == factors[-1] else -1
>>> factors.extend(n // f for f in factors[start::-1])
>>> factors
[1, 5, 13, 25, 65, 325]

推荐阅读