为了账号安全,请及时绑定邮箱和手机立即绑定

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

/ 猿问

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

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

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

我可以创建算法来完成这项工作,但我认为编码很差,并且执行大量数据的结果需要很长时间。


查看完整描述

3 回答

?
尚方宝剑之说
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摆脱其中一个。


查看完整回答
反对 回复 2019-07-29
?
凤凰求蛊

通过检查奇偶校验,可以使任意奇数的运行时间缩短约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,100,1)

这里没有显着差异,但数字越大,优势显而易见:

X =范围(1,100000,1000)(仅奇数) X =范围(1,100000,1000)(仅奇数)

X =范围(2,100000,100)(仅偶数) X =范围(2,100000,100)(仅偶数)

X =范围(1,100000,1001)(交替奇偶校验) X =范围(1,100000,1001)(交替奇偶校验)


查看完整回答
反对 回复 2019-07-29
?
呼唤远方

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%。


查看完整回答
反对 回复 2019-07-29

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信