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

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).

Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.

Разберемся как найти НОД двух чисел в Python. 

НОД с использованием функции gcd()

gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.

Синтаксис:

 
gcd(a, b) 

Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().

Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.

math_fun.py

 
# create a program to print the gcd of two number in python using the math.gcd() function. 
import math 
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number 
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48)) 
a = 60 # assign the number to variable a 
b = 48 # assign the number to variable b 
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function. 
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number 
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18)) 
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48)) 

Выход:

В приведенном выше примере функция math.gcd() генерирует НОД двух заданных чисел. В функции gcd() a и b передаются в качестве аргумента, который возвращает наибольший общий делитель двух целых чисел, полностью разделяя числа.

НОД с использованием рекурсии

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

Псевдокод алгоритма

Шаг 1: Возьмите два входа, x и y, от пользователя.

Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.

Шаг 3: Если второе число равно нулю(0), возвращается первое число.

Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.

Шаг 5: Вызовите или назначьте gcd_fun() переменной.

Шаг 6: Отобразите НОД двух чисел.

Шаг 7: Выйдите из программы.

Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.

gcdRecur.py

 
# write a program to understand the GCD of two number in python using the recursion. 
def gcd_fun(x, y): 
    if(y == 0): # it divide every number 
        return x  # return x 
    else: 
        return gcd_fun(y, x % y) 
x =int(input("Enter the first number: ")) # take first no.  
y =int(input("Enter the second number: ")) # take second no.  
num = gcd_fun(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

Нахождение НОД с помощью цикла

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

gcdFile.py

 
def GCD_Loop( a, b): 
    if a > b:  # define the if condition 
        temp = b 
    else: 
        temp = a 
    for i in range(1, temp + 1): 
        if(( a % i == 0) and(b % i == 0 )): 
            gcd = i 
    return gcd 
x = int(input(" Enter the first number: ") ) # take first no.  
y =int(input(" Enter the second number: ")) # take second no.  
num = GCD_Loop(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

Как мы видим в приведенной выше программе, мы берем два значения в качестве входных и передаем эти числа в функцию GCD_Loop(), чтобы вернуть GCD.

Алгоритм Евклида

Алгоритм Евклида – эффективный метод нахождения наибольшего общего делителя двух чисел. Это самый старый алгоритм, который делит большее число на меньшее и берет остаток. Опять же, он делит меньшее число от остатка, и этот алгоритм непрерывно делит число, пока остаток не станет 0.

Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.

Псевдокод алгоритма Евклида

Шаг 1: Есть два целых числа, например a и b.

Шаг 2: Если a = 0, то НОД(a, b) равен b.

Шаг 3: Если b = 0, НОД(a, b) равен a.

Шаг 4: Найти mod b.

Шаг 5: Предположим, что a = b и b = R.

Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.

Шаг 7: GCD = b и затем распечатайте результат.

Шаг 8: Остановите программу.

Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.

Euclid.py

 
# Create a program to find the GCD of two number in python using the Euclid's Algorithm. 
def find_hcf(a,b): 
    while(b): 
        a, a = b, a % b 
        return a 
a = int(input(" Enter the first number: ") ) # take first no.  
b = int(input(" Enter the second number: ")) # take second no.  
num = find_hcf(a, b) # call the find_hcf() to get the result 
print("  The HCF of two number a and b is ") 
print(num) # call num 

Выход:

Простые делители числа 13195 – это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?

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

Тут нужны несколько замечаний:

• Простое число по определению делится лишь на 1 и само на себя.
• При этом не обязательно для проверки делить на все числа от 1 до самого числа, т.к. если число вообще делится, то его можно представить в виде произведения двух чисел a*b, при это чем больше a, тем меньше b. После того как они сравняются (a==b), множители будут повторяться, т.е. a начнет принимать значения, которые ранее принимало b и наоборот.
• Таким образом в функции число n для проверки делится на все числа до квадратного корня из проверяемого числа включительно.
• Если встречается делитель, который нацело делит проверяемое число n, то работа функции прерывается оператором break и возвращается результат False
• Если по окончании перебора всего ряда ни одно из чисел не делит проверяемое число n нацело, значит оно является простым и функция возвращает True

Функция div_number(n) определяет максимальный делитель числа

• Предполагается, что число n можно разложить на два множителя a*b
• Число n последовательно делится на с каждой итерацией увеличивающееся (i+=1) число i
• Как только число n делится без остатка искомый максимальный делитель найден

Работа самой программы

• Вычисляется максимальный делитель числа N с помощью функции div_number(N)
• Полученный результат проверяется с помощью функции is_simple(N)
• Если число простое, то работы программы заканчивается и выводится результат
• Если нет, то число очередной раз делится и вычисляется максимальный делитель уже от него

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

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))

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

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