python - 获得一个数字的所有除数的最佳方法是什么？

Question

这是非常愚蠢的方式:

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

我想要得到的结果和这个类似，但我想要一个更智能的算法(这个太慢太笨了:-)

我可以足够快地找到主要因素及其多重性。 我有一个以这种方式生成因子的生成器:

(因子1，多重性1)
(因子2，多重性2)
(因子3, 多重性3)
等等……

即

的输出

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 的所有除数需要 0.01 秒，而笨方法在我的机器上采用 39 秒，非常酷:D

更新 2: 不要再说这是 this 的副本邮政。计算给定数的除数不需要计算所有除数。这是一个不同的问题，如果您认为不是，请在维基百科上查找“除数函数”。在发布之前阅读问题和答案，如果您不明白主题是什么，请不要添加无用且已经给出的答案。

Answer 1

鉴于您的 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的效率。