Как быстро найти все делители числа python

If your PC has tons of memory, a brute single line can be fast enough with numpy:

N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out: 
array([      1,       2,       4,       5,       8,      10,      16,
            20,      25,      32,      40,      50,      64,      80,
           100,     125,     128,     160,     200,     250,     320,
           400,     500,     625,     640,     800,    1000,    1250,
          1600,    2000,    2500,    3125,    3200,    4000,    5000,
          6250,    8000,   10000,   12500,   15625,   16000,   20000,
         25000,   31250,   40000,   50000,   62500,   78125,   80000,
        100000,  125000,  156250,  200000,  250000,  312500,  400000,
        500000,  625000, 1000000, 1250000, 2000000, 2500000, 5000000])

Takes less than 1s on my slow PC.

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

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

Вот проблема, которую я недавно пытался решить: дано целое число n, каковы все его делители?

Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.

В итоге я написал кое-что с помощью itertools, и в моем коде используется несколько интересных моментов из теории чисел. Я не знаю, буду ли я возвращаться к нему снова, но я надумал написать эту статью, потому что мои попытки решить озвученный выше вопрос перетекли в довольно забавное упражнение.

Простейший подход

Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:

def get_all_divisors_brute(n):
    for i in range(1, int(n / 2) + 1):
        if n % i == 0:
            yield i
    yield n

На деле нам нужно дойти только до n/2, потому что все, что больше этого значения, гарантировано не может быть делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.

Этот код очень прост, и для малых значений n он работает достаточно хорошо, но он довольно неэффективен и медлителен в других случаях. По мере увеличения n время выполнения линейно увеличивается. Можем ли мы сделать лучше?

Факторизация

В моем проекте я работал в основном с факториалами. Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:

8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

Поскольку факториалы состоят преимущественно из небольших множителей, я решил попробовать получить список делителей, определив сначала наименьшие из них. В частности, я искал простые множители, то есть те, которые также являются простыми числами. (Простое число — это число, единственными делителями которого являются оно само и 1. Например, 2, 3 и 5 являются простыми, а 4 и 6 — нет).

Вот функция, которая находит простые делители числа n:

def get_prime_divisors(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n /= i
            yield i
        else:
            i += 1

    if n > 1:
        yield n

Это похоже на предыдущую функцию, использующую перебор делителей: мы продолжаем пробовать множители, и если находим подходящий, то делим на него. В противном случае мы проверяем следующее число. Это довольно стандартный подход к поиску простых множителей.

Теперь мы можем использовать этот метод для получения факторизации числа, то есть для его записи в виде произведения простых чисел. Например, факторизация числа 8! выглядит следующим образом:

8! = 2^7 × 3^2 × 5 × 7

Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.

В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его в виде произведения простых множителей. (Я не буду приводить здесь доказательство, но вы можете найти его в Википедии).

Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.

Переход от факторизации к делителям

Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:

import collections

def get_all_divisors(n):
    primes = get_prime_divisors(n)

    primes_counted = collections.Counter(primes)

    ...

Затем, давайте продолжим и возведем каждое простое число во все степени, которые могут появиться в возможном делителе n.

def get_all_divisors(n):
    ...
    divisors_exponentiated = [
        [div ** i for i in range(count + 1)]
        for div, count in primes_counted.items()
    ]

Например, для 8! представленный код выдаст нам следующее:

[
    [1, 2, 4, 8, 16, 32, 64, 128],  // 2^0, 2^1, ..., 2^7
    [1, 3, 9],  // 3^0, 3^1, 3^2
    [1, 5],
    [1, 7],
]

Затем, чтобы получить делители, мы можем использовать довольно удобную функцию itertools.product, которая принимает на вход итерабельные объекты и возвращает все возможные упорядоченные комбинации их элементов. В нашем случае она выбирает по одному числу из каждого списка с возведениями в степень, а затем, перемножая их вместе, мы получаем очередной делитель n.

import itertools

def calc_product(iterable):
    acc = 1
    for i in iterable:
        acc *= i
    return acc

def get_all_divisors(n):
    ...

    for prime_exp_combination in itertools.product(*divisors_exponentiated):
        yield calc_product(prime_exp_combination)

Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).

Собираем все вместе

Сложив все это, мы получим следующую функцию для вычисления делителей n:

import collections
import itertools


def get_prime_divisors(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n /= i
            yield i
        else:
            i += 1

    if n > 1:
        yield n


def calc_product(iterable):
    acc = 1
    for i in iterable:
        acc *= i
    return acc


def get_all_divisors(n):
    primes = get_prime_divisors(n)

    primes_counted = collections.Counter(primes)

    divisors_exponentiated = [
        [div ** i for i in range(count + 1)]
        for div, count in primes_counted.items()
    ]

    for prime_exp_combination in itertools.product(*divisors_exponentiated):
        yield calc_product(prime_exp_combination)

print(list(get_all_divisors(40320))) # 8!

Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.

При работе с числами в программировании зачастую бывает нужно найти количество делителей для данного числа. Например, при работе с задачами на поиск простых чисел или при вычислении наибольшего общего делителя. В этой статье мы рассмотрим несколько способов, как найти количество делителей числа в языке программирования Python.

Что такое делители числа

В математике делителем натурального числа называют все числа, на которые это число делится без остатка. Например, делителями числа 12 являются числа 1, 2, 3, 4, 6 и 12, так как 12 делится на каждое из этих чисел без остатка. Количество делителей числа может быть разным в зависимости от самого числа. Например, у числа 12 имеется 6 делителей, а у числа 17 только 2 делителя (1 и само число).

Нахождение количества делителей числа с помощью цикла и проверки на остаток от деления

Для нахождения количества делителей числа можно использовать цикл и проверку на остаток от деления. Идея заключается в том, что мы перебираем все числа от 1 до самого числа и проверяем, делится ли число на каждое из этих чисел без остатка. Если да, то это число является делителем и мы увеличиваем счетчик делителей на 1.

Вот пример кода на Python, который иллюстрирует этот подход:

num = int(input("Введите число: "))
count = 0

for i in range(1, num+1):
    if num % i == 0:
        count += 1

print("Количество делителей числа", num, "равно", count)

В этом примере мы сначала запрашиваем у пользователя число, затем проходим по всем целым числам от 1 до введенного числа (включительно) с помощью цикла for. Для каждого числа в этом диапазоне мы проверяем, является ли оно делителем введенного числа (то есть, делится ли число нацело на i). Если да, то увеличиваем счетчик делителей на 1. В конце выводим количество найденных делителей на экран.

Такой подход работает для любых чисел, включая большие числа. Однако, при больших числах он может работать медленно, поскольку требует перебора всех чисел от 1 до n. Далее мы рассмотрим более эффективные способы нахождения количества делителей числа.

Нахождение количества делителей числа с помощью математических свойств чисел

Используем свойство: Если число n имеет делитель d, то оно также имеет делитель n/d

Данный способ основан на математическом свойстве, что если число n имеет делитель d, то оно также имеет делитель n/d. Исходя из этого свойства, можно заметить, что достаточно искать делители только до квадратного корня числа n, так как все остальные делители можно получить путем деления n на найденный делитель до квадратного корня.

Таким образом, для нахождения всех делителей числа n, мы можем использовать цикл от 1 до int(sqrt(n))+1, и проверять, является ли i делителем n, если да, то добавлять i и n/i в список делителей.

Например, для числа n=100, квадратный корень из него равен 10. Поэтому, достаточно проверить делители от 1 до 11 (включая 10). Если делитель найден, то мы можем добавить его и соответствующий делитель, найденный путем деления n на найденный делитель, в список делителей. Таким образом, делители числа 100 будут: [1, 2, 4, 5, 10, 20, 25, 50, 100].

Вот пример кода на Python, который использует данный подход

import math

def count_divisors(num):
    # Инициализация счетчика делителей
    div_count = 0

    # Находим квадратный корень из числа
    sqrt_num = int(math.sqrt(num))

    # Проверяем числа от 1 до квадратного корня num
    for i in range(1, sqrt_num + 1):
        if num % i == 0:
            # Если i является делителем, увеличиваем счетчик на 1
            div_count += 1

            # Проверяем, является ли num/i также делителем (чтобы избежать дублирования)
            if i != num // i:
                div_count += 1

    # Возвращаем общее количество делителей
    return div_count

Эта функция принимает один аргумент num, который является целым числом. Она использует функцию sqrt() из модуля math, чтобы найти квадратный корень из числа, и затем проверяет все числа от 1 до этого корня на предмет деления на num. Если число делится без остатка, оно добавляется к счетчику делителей div_count. Затем функция проверяет, является ли num делителем num/i, чтобы избежать дублирования. Наконец, функция возвращает общее количество делителей.

Данный способ эффективнее, чем перебор всех чисел до n-1, так как число проверок уменьшается в два раза. Однако, при использовании больших чисел, лучше использовать другие методы, например, разложение на простые множители.

Используем разложение на простые множители

Другой способ нахождения количества делителей числа заключается в использовании его математических свойств. Если мы знаем разложение числа на простые множители, то количество делителей числа можно легко вычислить.

Действительно, пусть дано число n = p_1^k_1 * p_2^k_2 * … * p_m^k_m, где p_1, p_2, …, p_m — простые числа, а k_1, k_2, …, k_m — их степени. Тогда каждый делитель числа n можно представить в виде d = p_1^i_1 * p_2^i_2 * … * p_m^i_m, где 0 <= i_j <= k_j для всех j от 1 до m. Таким образом, общее количество делителей числа n равно произведению (k_1 + 1) * (k_2 + 1) * … * (k_m + 1).

Для примера, давайте рассмотрим число 24. Его разложение на простые множители выглядит так: 24 = 2^3 * 3^1. Тогда количество делителей числа 24 равно (3 + 1) * (1 + 1) = 8. Это означает, что у числа 24 есть 8 делителей, а именно: 1, 2, 3, 4, 6, 8, 12 и 24.

Для вычисления количества делителей числа с помощью его разложения на простые множители в Python, нам необходимо воспользоваться функцией factorize() из библиотеки sympy. Она разлагает число на простые множители и возвращает список кортежей, каждый из которых содержит простой множитель и его степень. Затем мы можем вычислить количество делителей по формуле, описанной выше, и вернуть результат.

Вот пример кода, использующий функцию factorize() из библиотеки sympy для нахождения количества делителей числа:

from sympy import factorint

def count_divisors(n):
    factors = factorint(n)
    count = 1
    for factor in factors.values():
        count *= (factor + 1)
    return count

n = 24
print(f"Количество делителей числа {n}: {count_divisors(n)}")

Здесь мы сначала импортируем функцию factorint() из библиотеки sympy. Затем определяем функцию count_divisors(), которая принимает на вход число n и возвращает количество его делителей. Внутри функции мы используем функцию factorint() для разложения числа на простые множители и получаем словарь, где ключами являются простые множители, а значениями — их степени. Далее мы вычисляем количество делителей числа с помощью формулы, основанной на свойствах простых множителей, и возвращаем результат.

Затем мы просто вызываем функцию count_divisors() для числа 24 и выводим результат на экран. В данном случае результат будет равен 8, что соответствует количеству делителей числа 24 (1, 2, 3, 4, 6, 8, 12 и 24).