在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]，并在一个长长的清单一起加入他们。

在[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0返回两个因素，如果当你除以其余n由较小的一个是零（它并不需要检查较大的一个过;它只是获取除以n由较小的一个。）

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