Pythonの因数分解

Question

私は素数の指数とその指数の辞書があれば、数値のすべての整数因子をリストする最良の方法を知りたいのです。例えば
我々が持っている場合、{2：3,3：2,5：1}（2^3 * 3^2 * 5 = 360）
それから私は書くことができる：

for i in range(4): 
    for j in range(3): 
    for k in range(1): 
     print 2**i * 3**j * 5**k 

しかし、ここを私は3つのループがひどいです。任意の分解を辞書オブジェクト引数として与えられた関数にこれを抽象化することは可能ですか？

Answer 1

まあ、だけでなく、あなたは3つのループを持っていますが、あなたが持っている場合は、このアプローチは動作しません。以上の3つの要因:)

1つの可能な方法：あなたのワーキングセットは、（1,3）であれば、とに適用する：

def genfactors(fdict):  
    factors = set([1]) 

    for factor, count in fdict.iteritems(): 
     for ignore in range(count): 
      factors.update([n*factor for n in factors]) 
      # that line could also be: 
      # factors.update(map(lambda e: e*factor, factors)) 

    return factors 

factors = {2:3, 3:2, 5:1} 

for factor in genfactors(factors): 
    print factor 

また、あなたは内側のループでいくつかの作業の重複を避けることができます2^3因子、我々はやっていた：

• (1,3) U (1,3)*2 = (1,2,3,6)
• (1,2,3,6) U (1,2,3,6)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) U (1,2,3,4,6,12)*2 = (1,2,3,4,6,8,12,24)

我々は第二の組を持っているどのように多くの重複を参照してください？

しかし、我々は代わりに行うことができます。

• (1,3) + (1,3)*2 = (1,2,3,6)
• (1,2,3,6) + ((1,3)*2)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) + (((1,3)*2)*2)*2 = (1,2,3,4,6,8,12,24)

ソリューションがセットなくても立派になります

def genfactors(fdict): 
    factors = [1] 

    for factor, count in fdict.iteritems(): 
     newfactors = factors 
     for ignore in range(count): 
      newfactors = map(lambda e: e*factor, newfactors) 
      factors += newfactors 

    return factors 

Answer 2

基本的には、ターゲット番号の各要素で構成されるセットです。あなたの例では、セットは{2 2 2 3 3 5}になります。その集合の各厳密な部分集合は、あなたの数の除数のうちの1つの因子分解です。その集合のすべての部分集合を生成することができれば、各部分集合の要素を一緒に乗算し、すべての整数除数を得ることができます。

コードはかなり分かりやすいはずです：因数分解を含むリストを生成し、そのリストのすべてのサブセットを生成します（ジェネレータを使用するためのボーナスポイント;標準ライブラリに関連する関数があると思います）。それから乗算してそこから行ってください。最適な方法で効率的ではありませんが、見栄えが良いです。 Pythonの2.6からitertools.productを使用して

Answer 3

：

#!/usr/bin/env python 
import itertools, operator 

def all_factors(prime_dict): 
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()] 
    for multipliers in itertools.product(*series): 
     yield reduce(operator.mul, multipliers) 

例：

print sorted(all_factors({2:3, 3:2, 5:1})) 

出力：

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 
72, 90, 120, 180, 360] 

Answer 4

はい。あなたはn個のループのために入れ子に必要なアルゴリズムを持っているときは、通常、再帰関数に変換することができます：

def print_factors(d, product=1): 
    if len(d) == 0:  # Base case: we've dealt with all prime factors, so 
     print product # Just print the product 
     return 
    d2 = dict(d)   # Copy the dict because we don't want to modify it 
    k,v = d2.popitem() # Pick any k**v pair from it 
    for i in range(v+1): # For all possible powers i of k from 0 to v (inclusive) 
         # Multiply the product by k**i and recurse. 
     print_factors(d2, product*k**i) 

d = {2:3, 3:2, 5:1} 
print_factors(d) 

Answer 5

私はblogged about thisを持っている、と（itertoolsなし）最速純粋なPythonはPythonのリストにティム・ピーターズポストから来て、ネストされた再帰的なジェネレータ使用しています：

def divisors(factors) : 
    """ 
    Generates all divisors, unordered, from the prime factorization. 
    """ 
    ps = sorted(set(factors)) 
    omega = len(ps) 

    def rec_gen(n = 0) : 
     if n == omega : 
      yield 1 
     else : 
      pows = [1] 
      for j in xrange(factors.count(ps[n])) : 
       pows += [pows[-1] * ps[n]] 
      for q in rec_gen(n + 1) : 
       for p in pows : 
        yield p * q 

    for p in rec_gen() : 
     yield p 

注それが書かれている方法は、それが取ることを辞書ではなく、素因数のリスト、すなわち{2 : 3, 3 : 2, 5 : 1}の代わりに[2, 2, 2, 3, 3, 5]です。