小编典典

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

all

有人可以向我解释一种在 Python(2.7)中找到数字的所有因子的有效方法吗?

我可以创建一个算法来做到这一点,但我认为它的编码很差,并且需要很长时间才能产生大量的结果。


阅读 109

收藏
2022-08-20

共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)))

这将很快返回一个 number 的所有因数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摆脱其中一个。

2022-08-20