在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 math import sqrtdef 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 timeitfrom math import sqrtfrom matplotlib.pyplot import plot, legend, showdef 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 =范围（1,100000,1000）（仅奇数） 

X =范围（2,100000,100）（仅偶数） 

X =范围（1,100000,1001）（交替奇偶校验） 

Answer 3

agf的答案非常酷。我想看看是否可以重写它以避免使用reduce()。这就是我想出的：

import itertools
flatten_iter = itertools.chain.from_iterabledef factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

我还尝试了一个使用棘手的生成器函数的版本：

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

我通过计算计时：

start = 10000000end = start + 40000for n in range(start, end):
    factors(n)

我跑了一次让Python编译它，然后在time（1）命令下运行三次并保持最佳时间。

• 减少版本：11.58秒

• itertools版本：11.49秒

• 棘手的版本：11.12秒

请注意，itertools版本正在构建一个元组并将其传递给flatten_iter（）。如果我更改代码来构建列表，它会稍微减慢：

• iterools（列表）版本：11.62秒

我相信棘手的生成器函数版本在Python中是最快的。但它并不比降低版本快得多，根据我的测量值大约快4％。