获得一个数的所有除数的最佳方法是什么? [英] What is the best way to get all the divisors of a number?

问题描述

这是非常愚蠢的方式:

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

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

The result I'd like to get is similar to this one, but I'd like a smarter algorithm (this one it's too much slow and dumb :-)

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

I can find prime factors and their multiplicity fast enough. I've an generator that generates factor in this way:

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

(factor1, multiplicity1)
(factor2, multiplicity2)
(factor3, multiplicity3)
and so on...

即

for i in factorGenerator(100):
    print i

是:

(2, 2)
(5, 2)

我不知道这对我想做的事情有多大用处(我为其他问题编写了代码)，无论如何我想要一个更聪明的方法

I don't know how much is this useful for what I want to do (I coded it for other problems), anyway I'd like a smarter way to make

for i in divisorGen(100):
    print i

输出:

1
2
4
5
10
20
25
50
100

<小时>

更新: 非常感谢 Greg Hewgill 和他的聪明方式":)计算 100000000 的所有除数用他的方式计算了 0.01 秒，而笨方法在我的机器上使用了 39 秒，非常酷:D

---

UPDATE: Many thanks to Greg Hewgill and his "smart way" :) Calculating all divisors of 100000000 took 0.01s with his way against the 39s that the dumb way took on my machine, very cool :D

更新 2: 不要说这是 此 帖子.计算给定数的除数不需要计算所有的除数.这是一个不同的问题，如果您认为不是，那么请在维基百科上查找除数函数".发帖前请阅读问题和答案，如果您不明白主题是什么，请不要添加无用且已经给出的答案.

UPDATE 2: Stop saying this is a duplicate of this post. Calculating the number of divisor of a given number doesn't need to calculate all the divisors. It's a different problem, if you think it's not then look for "Divisor function" on wikipedia. Read the questions and the answer before posting, if you do not understand what is the topic just don't add not useful and already given answers.

推荐答案

给定你的 factorGenerator 函数，这里有一个 divisorGen 应该可以工作:

Given your factorGenerator function, here is a divisorGen that should work:

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

The overall efficiency of this algorithm will depend entirely on the efficiency of the factorGenerator.

这篇关于获得一个数的所有除数的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！