аватар question@mail.ru · 01.01.1970 03:00

алгоритм поиска всех делителей числа

День! решая пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [1,2,4,8], а не [2,2,2] - список делителей. Я переписал этот алгоритм наново, прошу ""старших товарищей"" подсказать как улучшить. Если есть время ))

def divisorss(n):    from collections import Counter    ls = get_ls(n)                  # for n=1568 -> ls = [2, 2, 2, 2, 2, 7, 7]    pairs = dict(Counter(ls))       #  {2: 5, 7: 2}    from itertools import product, starmap    from operator import mul    from functools import reduce    #  список всех различных делитей числа    bases = [b for b in pairs.keys()]   # [2, 7]    #  список степеней, в которые возводятся уникальные делители для получения числа      powers = [[i for i in range(k+1)] for k in pairs.values()]    # генерирование всех наборов для получения делителей исходного числа    multi = product(*powers)    #  сцепка списка оснований с возможными вариантами степеней    wrk = (zip(bases,power) for power in multi)    # наборы чисел, которые нужно перемножить для получения делителя    rezzz = (starmap( pow, row) for row in wrk)    # возвращение списка всех делителей    retu [reduce(mul,i) for i in rezzz]

например divisorss(1568) возвращает [1, 7, 49, 2, 14, 98, 4, 28, 196, 8, 56, 392, 16, 112, 784, 32, 224, 1568]

Функция get_ls(n) дает соответственно список разложения числа на произведение делителей

например такая:

def get_ls(n):    """"""Разложить число на множители""""""    #result = [1]    result = []    i = 2    while i*i <= n:        if n % i == 0:            n //= i            result.append(i)        else:            i += 1    if n > 1:        result.append(n)    retu result

что можно улучшить?
Ну например, что лучше - reduce из functools или accumulate из itertools. Ну и вообще по алгоритму.

Понятно, что улучшения типа

retu [reduce(mul,i) for i in (starmap(pow, row) for row in (zip(bases,power) for power in product(*powers)))] 

не интересны.

аватар answer@mail.ru · 01.01.1970 03:00

А если в одну строку через lambda-функцию:

from itertools import chaindivs = lambda n: chain(*((d, n // d) for d in range(1, int(n ** 0.5) + 1) if n % d == 0))print(list(divs(1568)))

Результат:

[1, 1568, 2, 784, 4, 392, 7, 224, 8, 196, 14, 112, 16, 98, 28, 56, 32, 49]

Обновление, более громоздкий вариант:

def primes():    def is_odd_prime(n):        if n % 3 == 0: retu False        i, w = 5, 2        while i * i <= n:             if n % i == 0: retu False             i += w             w = 6 - w        retu True    n, w = 5, 2    yield from (2, 3, n)    while True:        n += w        if n < 25 or is_odd_prime(n): yield n        w = 6 - wdef prime_facts(n):    for p in primes():        if n < p * p: break        t = n        while t % p == 0:            t //= p            yield p        def facts(n):    dd, tt = [1], []    for p in primes():        if n < p * p: break        t, e = n, 1        while t % p == 0:            tt += [d * p ** e for d in dd]            t //= p            e += 1        if e > 1:            dd += tt            del tt[:]    if n != dd[-1]:        dd += [n // d for d in dd]    retu ddn = 600851475143print(facts(n))
[71, 1471, 839, 6857, 486847, 10086647, 59569, 104441, 1234169, 5753023, 408464633, 716151937, 87625999, 8462696833, 1, 600851475143]

Демо на .

Последние

Похожие