在 Python 中查找数字的所有因子的最有效方法是什么？

Question

有人可以向我解释一种在 Python (2.7) 中查找数字所有因数的有效方法吗？

我可以创建一个算法来执行此操作，但我认为它的编码很差，并且需要很长时间才能为大量结果生成结果。

原文由 Adnan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

from functools import reduce

def factors(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

这将很快返回一个数字 n 的所有因数。

为什么平方根作为上限？

sqrt(x) * sqrt(x) = x 。因此，如果这两个因数相同，则它们都是平方根。如果你使一个因素变大，你必须使另一个因素变小。这意味着两者之一将始终小于或等于 sqrt(x) ，因此您只需搜索到该点即可找到两个匹配因子之一。然后，您可以使用 x / fac1 获取 fac2 。

reduce(list.__add__, ...) 正在获取 [fac1, fac2] 的小列表，并将它们连接成一个长列表。

[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 返回一对因子，如果你将 n 除以较小的一个为零（它也不需要检查较大的一个；它只是通过将 n 除以较小的那个。）

外面的 set(...) 正在去除重复项，这只发生在完美的正方形上。对于 n = 4 ，这将返回 2 两次，因此 set 摆脱其中之一。

原文由 agf 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

@agf 提供的解决方案很棒，但通过检查奇偶校验，可以使任意 奇数 的运行时间加快约 50%。由于奇数的因数本身总是奇数，因此在处理奇数时没有必要检查它们。

我刚刚开始自己解决 Project Euler 难题。在某些问题中，在两个嵌套的 for 循环中调用除数检查，因此该函数的性能至关重要。

将这一事实与 agf 的优秀解决方案相结合，我最终得到了这个功能：

 from functools import reduce
from math import sqrt
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

但是，对于较小的数字 (~ < 100)，此更改的额外开销可能会导致函数花费更长的时间。

我进行了一些测试以检查速度。下面是使用的代码。为了生成不同的图，我相应地更改了 X = range(1,100,1) 。

 import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = 范围 (1,100,1)

这里没有显着差异，但数字越大，优势就越明显：

X = range(1,100000,1000)（只有奇数）

X = range(2,100000,100)（仅限偶数）

X = range(1,100000,1001)（交替奇偶校验）

原文由 Steinar Lima 发布，翻译遵循 CC BY-SA 4.0 许可协议