获取一个数字的所有因子的最佳方法是什么？

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：别再说这是这个帖子的重复问题了。计算一个给定数字的因数个数并不需要计算所有的因数。这是一个不同的问题，如果你觉得不是，那就去维基百科查查“因数函数”。在发帖之前先读一下问题和答案，如果你不明白主题，就不要添加无用的、已经给出的答案。

Answer 1

我觉得你可以在 math.sqrt(n) 这个值的时候就停止，而不是到 n/2。

我给你举个例子，这样你能更容易理解。现在 sqrt(28) 的值是 5.29，所以 ceil(5.29) 就是 6。如果我在 6 的时候停止，就能找到所有的因数。怎么做到呢？

先看看代码，然后再看图片：

import math
def divisors(n):
    divs = [1]
    for i in range(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    divs.extend([n])
    return list(set(divs))

现在，看看下面的图片：

假设我已经把 1 加入了我的因数列表，然后我从 i=2 开始。

所以在所有的循环结束时，我把商和因数都加到了我的列表里，这样 28 的所有因数就都找到了。

来源： 如何确定一个数字的因数

Answer 2

为了更好地理解Shimi说的内容，你的循环只需要从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

根据你提供的 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 的效率。