алгоритм поиска всех делителей числа
📁 функция, список, python, пример
День! решая пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [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)))] не интересны.
А если в одну строку через 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]Демо на .
Войдите чтобы оставить ответ
Блоги
Как поддерживать навыки программирования на Python
Generics в C++: шаблоны, зачем нужны и как использовать