Как найти максимальное количество делителей python

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

https://zaochnik.com/spravochnik/matematika/delimost/nahozhdenie-vseh-delitelej-chisla/

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

import math

def countDividers(n):
    if n <= 0: return 0 # условно будем так считать
    if n == 1: return 1

    k = 2 # делителей изначально 2, само число и единица.
    for i in range(2, round(math.sqrt(n)) + 1): 
        if n % i == 0:
            k += 1 if i == n // i else 2 #считаем и делитель и частное, если они не совпадают
    return k

def maxDividersCountAtRange(m , n):
    if m > n : m, n = n, m # меняем местами если m > n, только для учебных програм

    maxDivs = 0 #
    numberWithMaxDivs = [] #список чисел с максимальным числом делителей
    for i in range(m, n): #идем по интервалу
        d = countDividers(i) #записываем результат в переменную для оптимизации
        if d > maxDivs: #ищем максимум
            maxDivs = d
            numberWithMaxDivs = [] #очищаем список при изменении максимума
        if d == maxDivs:
            numberWithMaxDivs.append(i) #добавляем число в список

    return maxDivs, numberWithMaxDivs

print(maxDividersCountAtRange(20,80))

Ввод и красивый вывод можно дописать самостоятельно

Питон знаю мало, так что правки приветствуются

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

У Вас M и N – какие числа? Вот как будет с натуральными числами и оптимизацией по нахождению количества делителей:

 def deli(n): 
    l, m = 0, int(n**0.5) 
    for i in range(1, m + 1): 
	if n % i == 0: l += 2 
    if m * m == n: l -= 1 
    return l 
while True: 
    M, N = map(int, input('M N: ').split()) 
    maxi, num = 0, [] 
    for i in range(M, N + 1): 
	d = deli(i) 
	if d > maxi: maxi = d; num = [i] 
	elif d == maxi: num.append(i) 
    print('Количество делителей:', d) 
    print(*num) 

Как видно, выводятся всё числа диапазона [M;N], для которых количество делителей максимально. Количество делителей каждого натуральное числа i определяется так: в цикле по натуральным числам j от 1 до m=√i включительно проверяется делимость i на j, если i делится на j, то количество делителей увеличивается на 2, в конце цикла проверяется условие m²=i – если имеет место равенство, количество делителей уменьшается на 1. Сложность алгоритма ~ Σ(i=M;N)√i. Для диапазонов [M;N] шириной порядка миллионов и без того оптимизированную программу надо будет оптимизировать ещё больше, иначе будет всё медленно считаться, а безо всякой оптимизации, даже, например, такой простой как у меня, вообще всё начинает виснуть, причём ни при никаких ни при миллионах, а всего лишь при скольких-то там тысячах…

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