有人可以向我解释一种在 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)))
这将很快返回一个 number 的所有因数n。
n
为什么以平方根为上限?
sqrt(x) * sqrt(x) = x. 因此,如果这两个因素相同,它们都是平方根。如果你让一个因素变大,你必须让另一个因素变小。这意味着两者之一将始终小于或等于sqrt(x),因此您只需搜索到该点即可找到两个匹配因子之一。然后您可以x / fac1使用fac2.
sqrt(x) * sqrt(x) = x
sqrt(x)
x / fac1
fac2
reduce(list.__add__, ...)正在获取一些小列表并将[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较小的因子来得到。)
[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0
set(...)外部正在消除重复项,这仅发生在完美的正方形中。对于n = 4,这将返回2两次,因此set摆脱其中一个。
set(...)
n = 4
2
set