4

День! решая задачу пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [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)
    # возвращение списка всех делителей
    return [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)
    return result

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

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

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

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

3
  • Я не понял что делает функция divisorss(). PS. И называется она неправильно, привыкайте называть функции по стандарту - первое слово должно быть глаголом. 20 ноя 2019 в 6:39
  • @Эникейщик это для меня печально. Значит не умею писать комментарии. выводит для числа список всех чисел, на которое оно делится. например, для 360 ls = [2, 2, 2, 3, 3, 5] divisorss возвращает [1, 5, 3, 15, 9, 45, 2, 10, 6, 30, 18, 90, 4, 20, 12, 60, 36, 180, 8, 40, 24, 120, 72, 360] то есть все числа на которые делится 360 нацело 20 ноя 2019 в 7:48
  • 2^0 * 3^0 * 5^0 = 1 ........................................................................................................ 2^0 * 3^0 * 5^1 =5 ............. 2^0 * 3^1 * 5^0 = 3 ................................................................................ 2^0 * 3^1 * 5^1 = 15 ...................... и т.д. ................................................. 2^3 * 3^2 * 5^1 = 360 20 ноя 2019 в 8:01

3 ответа 3

3

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

from itertools import chain
divs = 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: return False
        i, w = 5, 2
        while i * i <= n:
             if n % i == 0: return False
             i += w
             w = 6 - w
        return 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 - w

def 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]
    return dd

n = 600851475143
print(facts(n))
[71, 1471, 839, 6857, 486847, 10086647, 59569, 104441, 1234169, 5753023, 408464633, 716151937, 87625999, 8462696833, 1, 600851475143]

Демо на Rextester.

4
  • ух ты! красиво, хоть и так же медленно)) 21 ноя 2019 в 10:25
  • Предлагаю протестировать 2-ой вариант: rextester.com/edit/VQRT97194. 21 ноя 2019 в 20:31
  • по вашей ссылке - Requested page not found. Добавьте код в еще один ответ. Я по любому его плюсону )) 21 ноя 2019 в 20:41
  • Похоже без https:/ ссылка не работает. Почему эта часть исчезла - вопрос к сайту :) Ответ дополнил. 22 ноя 2019 в 8:36
1

Я бы нашел все делители вот так:

  1. Сначала бы перебрал все числа от 1 до квадратного корня из числа, округленного в большую сторону. И записал бы в список все числа, на которые без остатка делится число. Это будет первая половина всех делителей.

  2. Последующие числа я бы уже не проверял, а просто разделил число на все делители из первой половины и записал бы результаты в список. Это была бы вторая половина всех делителей. Единственный момент, если у чисeл квадратный корень - это целое число, то он попадет и в первый и во второй список, поэтому проверяю тут, каждое из числе уже не содержится в первом списке.

  3. Возвращаем результирующий список (конкатенация первой и второй половины).

from math import ceil, sqrt

def get_all_dividers(num):

    first_half_dividers = [x for x in range(1, ceil(sqrt(num)) + 1)
                           if num % x == 0]

    second_half_dividers = [int(num / x) for x in reversed(first_half_dividers)
                            if int(num / x) not in first_half_dividers]

    return first_half_dividers + second_half_dividers

print(get_all_dividers(16)) # [1, 2, 4, 8, 16]

Правда это только для положительных чисел подойдет, конечно :)

5
  • мдя. ваш алгоритм куда очевиднее и скорость на разных числах по разному. на одних мой быстрее, на других ваш. к слову, я хотел улучшения по иблиотекам, ну да ладно )) в вашем варианте возможно проще было воспользоваться множествами, чтоб в цикле не проверять... хотя кто знает, что быстрее )) 20 ноя 2019 в 8:17
  • @VasylKolomiets на больших числах ваш алгоритм быстрее. Но какие числа вы собираетесь проверять?) Не будет ли это экономией на спичках? Или это просто спортивный интерес у вас? 20 ноя 2019 в 8:20
  • это просто задачки для будущих учеников. на модули collections itertools functools 20 ноя 2019 в 8:26
  • да, взял n=2^10*3^10*5^10*7, мой алгоритм - 9ms, ваш - 13.5 s. На бОльших числах вообще жесть... 20 ноя 2019 в 11:24
  • 3
    Попробуйте до квадратного корня вычислить по вашей схеме, а после - моим)) Может быть еще быстрее будет, но это не точно. 20 ноя 2019 в 12:06
0

Для нечётных чисел можно исключить из проверки все чётные - через шаг в диапазоне цикла (1, n+1, 2)).

1
  • 2
    Ваш ответ можно улучшить с помощью дополнительной информации. Пожалуйста, нажмите править для добавления подробностей, например, цитат или документации, чтобы другие могли подтвердить правильность вашего ответа. Вы можете найти дополнительную информацию о том, как писать хорошие ответы в Справке. 1 июл 2022 в 0:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.