Как найти число по количеству делителей python

При работе с числами в программировании зачастую бывает нужно найти количество делителей для данного числа. Например, при работе с задачами на поиск простых чисел или при вычислении наибольшего общего делителя. В этой статье мы рассмотрим несколько способов, как найти количество делителей числа в языке программирования 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).

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

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

Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.

Нахождение делителей числа

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

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

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

Пользователь вводит целое число, делителей которого будет искать программа, тогда код выглядит так:

numb = int(input("Введите целое число: "))
print("Результат:", end = " ")
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        print(i, end = " ")

Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:

Введите целое число: 625
Результат: 125 25 5

Простые делители числа

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

Программа построена по следующему алгоритму:

1. Обнулить счётчик.
2. В цикле искать делители.
3. Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
4. Если найден, увеличить счётчик.
5. Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
6. Перейти на следующую итерацию внешнего цикла.

Цикл теперь выглядит так:

numb = int(input("Введите целое число: "))
print("Простые:", end = " ")
for i in range(numb - 1, 1, -1):
    is_simple = 0 # Счётчик
    if (numb % i == 0):
        for j in range(i - 1, 1, -1):
            if (i % j == 0):
                is_simple = is_simple + 1 # Увеличиваем, если находим делитель
        if (is_simple == 0): # Если делителей не было найдено, выводим
            print(i, end = " ")

Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.

Результат работы программы:

Введите целое число: 63
Простые: 7 3

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

Сумма делителей

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

Код программы:

numb = int(input("Введите целое число: "))
sum_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        sum_of_dividers += i
print("Сумма:", sum_of_dividers)

Результат выполнения кода:

Введите целое число: 63
Сумма: 40

Количество делителей

Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие «numb % i == 0» будет выполняться.

numb = int(input("Введите целое число: "))
count_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        count_of_dividers += 1
print("Количество равно:", count_of_dividers)

Результаты выполнения программы:

Введите целое число: 63
Количество равно: 4

Максимальный и минимальный делитель

Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider. В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.

Код программы:

numb = int(input("Введите целое число: "))
min_divider = numb
max_divider = 1
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        if (min_divider > i):
            min_divider = i
        if (max_divider < i):
            max_divider = i
print("Минимальный равен:", min_divider)
print("Максимальный равен:", max_divider)

Результат выполнения:

Введите целое число: 63
Минимальный равен: 3
Максимальный равен: 21

Нахождение наименьшего и наибольшего делителя, подсчёт суммы делителей и их количества можно объединить в одну программу на Python. Это не должно вызвать каких-либо проблем или конфликтов, потому что программа работает с 4 независимыми переменными.