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

Question

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

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

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] 的小 list 并将它们组合成一个长长的列表。

[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0如果除以 n 时的余数，则返回一对因数除以较小的值为零(它也不需要检查较大的值；只需将 n 除以较小的值即可。)

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