得到一个数的所有除数的最佳方法是什么？

  • Z时代
  • 2024-01-10
  • 分类：问答

这是非常愚蠢的方式：

def divisorGenerator(n):
    for i in xrange(1,n/2+1):
        if n%i == 0: yield i
    yield n

我想要得到的结果与此类似，但是我想要一种更智能的算法（这个算法太慢而且太笨了:-)

我可以很快找到主要因素及其多样性。我有一个生成器以这种方式生成因子：

（factor1，multiplicity1）（factor2，multiplicity2）

（

factor3，multiplicity3）

等等…

即输出

for i in factorGenerator(100):
    print i

是：

(2, 2)
(5, 2)

我不知道这对我想做的事情有多大帮助（我为其他问题编写了代码），无论如何，我都希望有一种更聪明的制作方法

for i in divisorGen(100):
    print i

输出：

1
2
4
5
10
20
25
50
100

非常感谢格雷格·休吉尔（Greg Hewgill）和他的“聪明之道”

:)计算100000000的所有除数，用他的方式对付我的机器上愚蠢的方式所用的39岁时，花费了0.01秒。

别说这是这篇文章的重复。计算给定数的除数不需要计算所有除数。这是一个不同的问题，如果您认为不是这样，那么请在Wikipedia上查找“除数函数”。在发布之前，请先阅读问题和答案，如果您不明白主题是什么，请不要添加无用且已给出答案的内容。

回答：

给定您的factorGenerator函数，这是一个应该起作用的divisorGen：

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

该算法的整体效率将完全取决于factorGenerator的效率。

以上是 得到一个数的所有除数的最佳方法是什么？ 的全部内容， 来源链接： utcz.com/qa/405120.html

回到顶部