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

Question

有人能告诉我在Python（2.7）中，有什么高效的方法来找出一个数字的所有因子吗？

我可以写一个算法来实现这个功能，但我觉得我的代码写得不好，而且对于大数字来说，运行起来太慢了。

Answer 1

在SymPy这个库里，有一个非常强大的算法叫做 factorint：

>>> from sympy import factorint
>>> factorint(2**70 + 3**80) 
{5: 2,
 41: 1,
 101: 1,
 181: 1,
 821: 1,
 1597: 1,
 5393: 1,
 27188665321L: 1,
 41030818561L: 1}

这个算法运行时间不到一分钟。它会使用多种方法来解决问题，具体可以查看上面链接的文档。

一旦找到了所有的质因数，其他的因数就能很容易地计算出来。

---

需要注意的是，即使允许被接受的答案运行很长时间（也就是无限长），去分解上面的数字，对于某些大数字来说，它也会失败，比如下面这个例子。这是因为使用了不太严谨的 int(n**0.5)。举个例子，当 n = 10000000000000079**2 时，我们会得到

>>> int(n**0.5)
10000000000000078L

因为 10000000000000079 是一个质数，所以被接受的答案中的算法永远找不到这个因数。需要注意，这不仅仅是差了1，对于更大的数字来说，误差会更大。因此，在这种算法中，最好避免使用浮点数。

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 = range(1,100,1)

在这里没有显著的差别，但在处理更大的数字时，优势就明显了：

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

X = range(2,100000,100)（只有偶数）

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

Answer 3

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 会去掉其中一个。