有人可以向我解释一种在 Python (2.7) 中找到数字的所有因数的有效方法吗?
我可以创建一个算法来执行此操作,但我认为它的编码很差,并且需要很长时间才能产生大量结果。
最佳答案
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
摆脱其中之一。
https://stackoverflow.com/questions/6800193/