1

我将素数分解作为字典：

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

使用该函数检索数字的所有除数的最佳 Python 方法是pf什么？随意使用itertools。

4

4 回答 4

4

像这样的东西也许

>>> 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])
于 2012-06-14T08:06:05.833 回答
0 
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)))
于 2012-06-14T08:17:00.553 回答
0

虽然这个答案并不过分pythonic，但它使用简单的递归来找到主要因素。

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}
于 2012-06-14T08:21:54.093 回答
0

单线：

>>> 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]
>>>
于 2012-06-14T09:32:21.280 回答