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

Question

这是非常愚蠢的方式：

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.01s。

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

Answer 1

给定您的factorGenerator函数，这是一个应该工作的divisorGen：def divisorGen(n):&nbsp; &nbsp; factors = list(factorGenerator(n))&nbsp; &nbsp; nfactors = len(factors)&nbsp; &nbsp; f = [0] * nfactors&nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)&nbsp; &nbsp; &nbsp; &nbsp; i = 0&nbsp; &nbsp; &nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; f[i] += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if f[i] <= factors[i][1]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; f[i] = 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i >= nfactors:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return该算法的整体效率将完全取决于factorGenerator的效率。

Answer 2

您应该只在1到n的平方根之间运行循环。然后找到对，执行n / i，这将覆盖整个问题空间。还应指出的是，这是一个NP或“困难”的问题。穷举搜索（您正在执行的方式）与保证答案的效果差不多。加密算法等使用此事实来帮助保护它们。如果有人要解决这个问题，那么我们目前大多数的“安全”通信，即使不是全部，也会变得不安全。Python代码：import mathdef divisorGenerator(n):    large_divisors = []    for i in xrange(1, int(math.sqrt(n) + 1)):        if n % i == 0:            yield i            if i*i != n:                large_divisors.append(n / i)    for divisor in reversed(large_divisors):        yield divisorprint list(divisorGenerator(100))应该输出如下列表：[1、2、4、5、10、20、25、50、100]

Answer 3

尽管已经有很多解决方案，但我确实必须发布此内容：）快速（在有很多主要因素和因数的情况下，比公认的解决方案快10倍以上）符合python3，python2和pypy码：def divisors(n):    # get factors and their counts    factors = {}    nn = n    i = 2    while i*i <= nn:        while nn % i == 0:            factors[i] = factors.get(i, 0) + 1            nn //= i        i += 1    if nn > 1:        factors[nn] = factors.get(nn, 0) + 1    primes = list(factors.keys())    # generates factors from primes[k:] subset    def generate(k):        if k == len(primes):            yield 1        else:            rest = generate(k+1)            prime = primes[k]            for factor in rest:                prime_to_i = 1                # prime_to_i iterates prime**i values, i being all possible exponents                for _ in range(factors[prime] + 1):                    yield factor * prime_to_i                    prime_to_i *= prime    # in python3, `yield from generate(0)` would also work    for factor in generate(0):        yield factor