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

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输出：124510202550100更新：非常感谢格雷格·休吉尔（Greg Hewgill）和他的“聪明之道” :)计算100000000的所有除数，而他的方式与我的机器上愚蠢的方式所用的39分相差0.01s。更新2：别说这是这篇文章的重复。计算给定数的除数的数量不需要计算所有除数。这是一个不同的问题，如果您认为不是这样，那么请在Wikipedia上查找“除数函数”。在发帖之前，请先阅读问题和答案，如果您不明白主题是什么，请仅添加没有用的已经给出的答案。

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

Answer 2

您应该只在1到n的平方根之间运行循环。然后找到对，执行n / i，这将覆盖整个问题空间。

还应指出的是，这是一个NP或“困难”的问题。穷举搜索（您正在执行的方式）与保证答案的效果差不多。加密算法等使用此事实来帮助保护它们。如果有人要解决这个问题，那么我们目前大多数的“安全”通信，即使不是全部，也会变得不安全。

Python代码：

import math

def 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 divisor

print 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