вещий способ получения списка делителей дал простые множители

У меня есть простые множители в качестве словаря:вещий способ получения списка делителей дал простые множители

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

Что такое лучший вещий способ для извлечения всех делителей числа, используя функцию pf? не стесняйтесь использовать itertools.

источник

2012-06-14 prongs

Не должно быть, что '{2: 1,5: 1}'? –

Да, я тоже был смущен вашим словарем. – user1413793

Я думаю, что формат dict - это фактор как ключ, а показатель - как значение - '2 ** 2 * 5 ** 2'. – PaulMcG

Что-то вроде этого, может быть,

>>> 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-14 08:06:05

Невозможно получить больше питоничности. –

+1, но учитывайте 'комбинации' вместо' перестановок'. – georg

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-14 08:17:00 prongs

Хотя этот ответ не слишком вещий он использует простую рекурсию, чтобы найти простые множители.

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-14 08:21:54

Вам нужно только выполнить поиск до x ** 0.5 (т. Е. Верхняя граница вашего xrange может быть x ** 0,5 + 1 вместо x/2, это дает вам лучшее время исполнения O). Кроме того, x/2 уже возвращает int (целочисленное деление по умолчанию обрабатывает результат). – user1413793

Исправлено это, спасибо за то, что на голову :-) –

Это должно быть x ** 0,5 + 1, потому что xrange не включает верхнюю границу. Например, в случае 9 вы хотите, чтобы xrange остановился на 3. То, как у вас есть это сейчас, будет остановлено на 2, а 9 - простое число. – user1413793

Однострочные:

>>> 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-14 09:32:21 Emmanuel

вещий способ получения списка делителей дал простые множители

ответ

Смежные вопросы