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

问题描述

这里是非常愚蠢的方式：

Here's the very dumb way:

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，multiplicity1）
（因子2，multiplicity2）
（factor3，multiplicity3）
等等...

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

即。输出

for i in factorGenerator(100):
    print i

是：

(2, 2)
(5, 2)

我不知道有多少是这个有用的东西我想要做的（I codeD用于其他问题），反正我想要一个更聪明的方法，使

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

输出这样的：

output this:

1
2
4
5
10
20
25
50
100

---

---

更新：非常感谢格雷格Hewgill和他的聪明的方式:) 计算100000000的所有除数了0.01秒，他的方法对了哑巴的方式把我的机器上，非常酷的39S：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：不要说这是<一个副本href="http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number">this职位。计算给定数目的因数的数目并不需要计算所有的除数。这是一个不同的问题，如果你认为它不是然后寻找在维基百科除数功能。阅读的问题和答案发布前，如果你不明白什么是只是不添加没有用的，并且已经给出答案的话题。

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屋！