[解決済み] ある数のすべての約数を求める最良の方法は何ですか？

質問

非常に間抜けな方法を紹介します。

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

UPDATEです。 Greg Hewgillと彼のquot;smart way"に感謝します:) 100000000 のすべての約数を計算するのに、私のマシンでは馬鹿げた方法で 39 秒かかったのに対して、彼の方法では 0.01 秒で済みました。

UPDATE 2: の重複というのはやめてください。 この の投稿です。与えられた数の約数を計算するのは、すべての約数を計算する必要はない。それは別の問題です、あなたがそうでないと思うなら、wikipediaで"除数関数"を探してみてください。投稿する前に質問と回答を読んでください。もしトピックが何であるか理解できない場合は、役に立たない回答や既に与えられた回答を追加しないでください。

どのように解決するのですか？

あなたの 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 .