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

Question

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

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

我可以创建算法来完成这项工作，但我认为编码很差，并且执行大量数据的结果需要很长时间。

Answer 1

from functools import reducedef 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摆脱其中一个。

Answer 2

通过检查奇偶校验，可以使任意奇数的运行时间缩短约50％。由于奇数的因子本身总是奇数，所以在处理奇数时没有必要检查它们。我刚刚开始自己解决Project Euler谜题。在某些问题中，在两个嵌套for循环内部调用除数检查，因此该函数的性能至关重要。将这一事实与agf优秀的解决方案相结合，我最终得到了这个功能：from&nbsp;math&nbsp;import&nbsp;sqrtdef&nbsp;factors(n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;step&nbsp;=&nbsp;2&nbsp;if&nbsp;n%2&nbsp;else&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;set(reduce(list.__add__, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;([i,&nbsp;n//i]&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;int(sqrt(n))+1,&nbsp;step)&nbsp;if&nbsp;n&nbsp;%&nbsp;i&nbsp;==&nbsp;0)))但是，对于较小的数字（〜<100），此更改的额外开销可能会导致函数花费更长时间。我跑了一些测试来检查速度。以下是使用的代码。为了产生不同的图，我相应地改变了X = range(1,100,1)。import&nbsp;timeitfrom&nbsp;math&nbsp;import&nbsp;sqrtfrom&nbsp;matplotlib.pyplot&nbsp;import&nbsp;plot,&nbsp;legend,&nbsp;showdef&nbsp;factors_1(n): &nbsp;&nbsp;&nbsp;&nbsp;step&nbsp;=&nbsp;2&nbsp;if&nbsp;n%2&nbsp;else&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;set(reduce(list.__add__, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;([i,&nbsp;n//i]&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;int(sqrt(n))+1,&nbsp;step)&nbsp;if&nbsp;n&nbsp;%&nbsp;i&nbsp;==&nbsp;0)))def&nbsp;factors_2(n): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;set(reduce(list.__add__, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;([i,&nbsp;n//i]&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;int(sqrt(n))&nbsp;+&nbsp;1)&nbsp;if&nbsp;n&nbsp;%&nbsp;i&nbsp;==&nbsp;0)))X&nbsp;=&nbsp;range(1,100000,1000)Y&nbsp;=&nbsp;[]for&nbsp;i&nbsp;in&nbsp;X: &nbsp;&nbsp;&nbsp;&nbsp;f_1&nbsp;=&nbsp;timeit.timeit('factors_1({})'.format(i),&nbsp;setup='from&nbsp;__main__&nbsp;import&nbsp;factors_1',&nbsp;number=10000) &nbsp;&nbsp;&nbsp;&nbsp;f_2&nbsp;=&nbsp;timeit.timeit('factors_2({})'.format(i),&nbsp;setup='from&nbsp;__main__&nbsp;import&nbsp;factors_2',&nbsp;number=10000) &nbsp;&nbsp;&nbsp;&nbsp;Y.append(f_1/f_2)plot(X,Y,&nbsp;label='Running&nbsp;time&nbsp;with/without&nbsp;parity&nbsp;check')legend()show()X =范围（1,100,1）&nbsp;这里没有显着差异，但数字越大，优势显而易见：X =范围（1,100000,1000）（仅奇数）&nbsp;X =范围（2,100000,100）（仅偶数）&nbsp;X =范围（1,100000,1001）（交替奇偶校验）&nbsp;

Answer 3

agf的答案非常酷。我想看看是否可以重写它以避免使用reduce()。这就是我想出的：import&nbsp;itertools flatten_iter&nbsp;=&nbsp;itertools.chain.from_iterabledef&nbsp;factors(n): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;set(flatten_iter((i,&nbsp;n//i)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;int(n**0.5)+1)&nbsp;if&nbsp;n&nbsp;%&nbsp;i&nbsp;==&nbsp;0))我还尝试了一个使用棘手的生成器函数的版本：def&nbsp;factors(n): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;set(x&nbsp;for&nbsp;tup&nbsp;in&nbsp;([i,&nbsp;n//i]&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;int(n**0.5)+1)&nbsp;if&nbsp;n&nbsp;%&nbsp;i&nbsp;==&nbsp;0)&nbsp;for&nbsp;x&nbsp;in&nbsp;tup)我通过计算计时：start&nbsp;=&nbsp;10000000end&nbsp;=&nbsp;start&nbsp;+&nbsp;40000for&nbsp;n&nbsp;in&nbsp;range(start,&nbsp;end): &nbsp;&nbsp;&nbsp;&nbsp;factors(n)我跑了一次让Python编译它，然后在time（1）命令下运行三次并保持最佳时间。减少版本：11.58秒itertools版本：11.49秒棘手的版本：11.12秒请注意，itertools版本正在构建一个元组并将其传递给flatten_iter（）。如果我更改代码来构建列表，它会稍微减慢：iterools（列表）版本：11.62秒我相信棘手的生成器函数版本在Python中是最快的。但它并不比降低版本快得多，根据我的测量值大约快4％。