Python的方式給出因式分解

Question

我有因式分解作爲字典：

>>>pf(100) 
>>>{2:2,5:2} 

什麼是檢索使用功能pf該號碼的所有除數最好的Python的方式？隨時可以使用itertools。

Answer 1

像這樣的事情也許

>>> from itertools import * 
>>> from operator import mul 
>>> d = {2:2,5:1} # result of pf(20) 
>>> l = list(chain(*([k] * v for k, v in d.iteritems()))) 
>>> l 
[2, 2, 5] 
>>> factors = set(chain(*(permutations(l, i) for i in range(1,len(l)+1)))) 
set([(2, 2, 5), (2,), (5,), (5, 2, 2), (2, 2), (2, 5), (5, 2), (2, 5, 2)]) 
>>> set(reduce(mul, fs, 1) for fs in factors) 
set([4, 2, 10, 20, 5]) 

Answer 2

from itertools import product 
def primeplus(): 
    """ 
    Superset of primes using the primes are a subset of 6k+1 and 6k-1. 
    """ 
    yield 2 
    yield 3 
    n=5 
    while(True): 
    yield n 
    yield n+2 
    n+=6 
def primefactorization(n): 
    ret={} 
    for i in primeplus(): 
    if n==1: break 
    while n%i==0: 
     ret[i]=ret.setdefault(i,0)+1 
     n=n//i 
    return ret 
def divisors(n): 
    pf=primefactorization(n) 
    keys,values=zip(*pf.items()) 
    return (reduce(lambda x,y:(x[0]**x[1])*(y[0]**y[1]),zip(keys,p1)+[(1,1)]) for p1 in product(*(xrange(v+1) for v in values))) 

Answer 3

雖然這個回答是不是太Python的，它使用簡單的遞歸發現的主要因素。

def find_factors(x): 
    for i in xrange(2, int(x ** 0.5) + 1): 
     if x % i == 0: 
      return [i] + find_factors(x/i) 
    return [x] 

print find_factors(13) # [13] 
print find_factors(103) # [103] 
print find_factors(125) # [5,5,5] 
print find_factors(1334234) # [2, 11, 60647] 

from collections import Counter 

print dict(Counter(find_factors(13))) # {13: 1} 
print dict(Counter(find_factors(103))) # {103: 1} 
print dict(Counter(find_factors(125))) # {5: 3} 
print dict(Counter(find_factors(1334234))) # {2: 1, 11: 1, 60647: 1} 

Answer 4

一個班輪：

>>> d = {3:4, 5:1, 2:2} 
>>> sorted(map(lambda p: reduce(mul, p), product(*map(lambda c: [c[0] ** i for i in range(c[1] + 1)], d.iteritems())))) 
[1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 27, 30, 36, 45, 54, 60, 81, 90, 108, 135, 162, 180, 270, 324, 405, 540, 810, 1620] 
>>>