Наименьший общий делитель как найти питон

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(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 

Выход:

Функции относящиеся к теории чисел.

В этом разделе представлены функции относящиеся к теории чисел.

Содержание:

• Факториал числа,
• Наибольший общий делитель целых чисел,
• Функция math.frexp(),
• Функция math.ldexp(),
• Абсолютное значение числа,
• Остаток от деления,
• Получить дробную и целую часть числа,
• Получить точную сумму элементов списка,
• Получить число x со знаком числа y,
• Сравнение в пределах указанной точности,
• Наименьшее общее кратное целых чисел,
• Следующее значение float после x по направлению к y,
• Наименьший значащий бит числа float.

math.factorial(x):

Функция math.factorial() возвращает факториал указанного числа x.

>>> import math
>>> math.factorial(5)
120

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

Если x не является целым числом или если x является отрицательным, то будет вызвано исключение ValueError.

Изменено в Python 3.9. Не рекомендуется передавать числа с плавающей запятой с целыми значениями (например, 5.0).

math.gcd(*integers):

Функция math.gcd() возвращает наибольший общий делитель указанных целочисленных аргументов *integers.

>>> import math
>>> math.gcd(3886, 9048)
# 58

# проверяем
>>> 3886/58, 9048/58
# (67.0, 156.0)

• Если какой-либо из аргументов не равен нулю, то возвращаемое значение является наибольшим положительным целым числом, которое является делителем всех аргументов:
• Если все аргументы равны нулю, то возвращаемое значение равно 0.
• функция math.gcd() вызванная без аргументов возвращает 0.

Указанные числа должны быть целыми типа int, но могут быть как положительными, так и отрицательными:

>>> import math
>>> math.gcd(-4, -8)
# 4
>>> math.gcd(-4, -8.8)
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: 'float' object cannot be interpreted as an integer

Изменено в Python 3.9: Добавлена ​​поддержка произвольного количества аргументов. Раньше поддерживалось только два аргумента.

math.frexp(x):

Функция math.frexp() возвращает кортеж из двух чисел (m, e) таких что x == m*2**e.

>>> import math
>>> math.frexp(123)
# (0.9609375, 7)
>>> 0.9609375*2**7
# 123.0

Число m принадлежит к типу float и всегда является таким, что 0.5 <= abs(m) < 1, даже для тех случаев, когда значением x является произвольная степень двойки. Число e всегда целое число int:

>>> math.frexp(0.25)
# (0.5, -1)
>>> math.frexp(64)
# (0.5, 7)

Если x равен 0, то будет возвращено (0.0, 0).

Данная функция используется тогда, когда представление чисел типа float не должно зависеть от архитектуры машины.

math.ldexp(x, i):

Функция math.ldexp() возвращает значение равное x*2**i, т.е. является обратной к функции math.frexp().

>>> import math
>>> math.ldexp(3, 4)
# 48.0
>>> math.ldexp(0.125, 8)
# 32.0

math.fabs(x):

Функция math.fabs() возвращает абсолютное значение, модуль числа x. Результат всегда тип float.

>>> import math
>>> math.fabs(-3)
3.0

Данная функция в отличии от встроенной функции abs() не обрабатывает комплексные числа.

math.fmod(x):

Функция math.fmod() возвращает остаток от деления числа x на число y, вычисленный так, как это определено в библиотеке math языка C.

>>> import math
>>> math.fmod(2.23, 0.2)
0.02999999999999986

Данная функция направлена на то, что бы результат был максимально приближен к значению x - n*y для некоторого целого числа n, что бы этот результат имел тот же знак, что и x, что бы разность x - n*y == abs(y).

Для чисел типа float данная функция является предпочтительнее чем команда x%y, которая в свою очередь является предпочтительной для чисел типа int. Так как для некоторых случаев, например при x = -1e-100 и x = 1e100, команда x%y может вообще выдать неправильный результат.

math.modf(x):

Функция math.modf() возвращает кортеж из двух чисел (f, w) где f это дробная, а w — целая часть числа x. Результат всегда имеет тип float.

>>> import math
>>> math.modf(3)
# (0.0, 3.0)
>>> math.modf(3.14)
# (0.14000000000000012, 3.0)

math.fsum(iterable):

Функция math.fsum() возвращает точную сумму значений в итерируемой последовательности iterable. Возвращаемый результат всегда типа float.

>>> import math
>>> sum([.1, .1, .1, .1, .1, .1, .1, .1, .1, .1])
# 0.9999999999999999
>>> math.fsum([.1, .1, .1, .1, .1, .1, .1, .1, .1, .1])
# 1.0

Может показаться, что эта сумма будет точной всегда, но на самом деле это не так:

>>> math.fsum([0.3, 0.3, 0.3])
0.8999999999999999

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

math.copysign(x, y):

Функция math.copysign() возвращает число c абсолютным значением x, но со знаком числа y. Возвращаемый результат всегда типа float

>>> import math
>>> math.copysign(14, -12)
# -14.0
>>> math.copysign(-14, 12)
# 14.0

На платформах, которые поддерживают нули со знаком функция math.copysign(1.0, -0.0) возвращает -1.0.

math.isclose(a, b, *, rel_tol=1e-09, abs_tol=0.0):

Функция math.isclose() возвращает True если в пределах указанной точности, числа a и b близки настолько, что их можно считать равными.

>>> import math
>>> x = 7
>>> y = 7.000000000000001
>>> x==y
# False
>>> math.isclose(x, y)
# True

Считать числа близкими или нет, определяют два аргумента rel_tol и abs_tol.

Аргумент rel_tol это относительный допуск, определяемый как максимально допустимая разница между числами a и b относительно большего из них по модулю. По умолчанию rel_tol=1e-09, что гарантирует, что числа a и b будут одинаковы, в пределах 9 десятичных цифр. Чтобы числа считались равными, если они, допустим, отличаются меньше чем на 0.1%, то достаточно установить rel_tol=0.001, но в любом случае данный параметр, должен быть больше нуля:

>>> y = 7.000001
>>> math.isclose(y, 6.999, rel_tol=0.001)
# True

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

Данная функция эквивалентна команде abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol). Значения inf, -inf считаются близкими только сами к себе, а NaN не является близким ни к одному значению, включая само NaN.

math.lcm(*integers):

Функция math.lcm() возвращает наименьшее общее кратное указанных целочисленных аргументов *integers.

• Если все аргументы отличны от нуля, то возвращаемое значение является наименьшим положительным целым числом, кратным всем аргументам.
• Если какой-либо из аргументов равен нулю, то возвращается значение 0.
• Функция math.lcm(), вызванная без аргументов возвращает 1.

Новое в Python 3.9.

math.nextafter(x, y):

Функция math.nextafter() возвращает следующее значение float после x по направлению к y.

Если x равно y, то функция возвращает y.

Примеры:

• math.nextafter(x, math.inf) идет вверх: в сторону положительной бесконечности.
• math.nextafter(x, -math.inf) идет вниз: в сторону минус бесконечности.
• math.nextafter(x, 0.0) стремится к нулю.
• math.nextafter(x, math.copysign(math.inf, x)) уходит от нуля.

Новое в Python 3.9.

Смотрите также математическую функцию math.ulp().

math.ulp(x):

Функция math.isclose() возвращает значение наименьшего значащего бита числа float x.

• Если x — NaN (не число), то вернет x.
• Если x отрицательный, то вернет ulp(-x).
• Если x — положительная бесконечность, то вернет x.
• Если x равен нулю, то вернет наименьшее положительное денормализованное представимое число float (меньше минимального положительного нормализованного числа float, sys.float_info.min).
• Если x равен наибольшему положительному представимому числу float, то вернет значение младшего значащего бита x, так что первое число float меньше x будет x - ulp(x).
• В противном случае (x — положительное конечное число) вернет значение младшего значащего бита x, так что первое число float больше x равно x + ulp(x).

ULP означает «Единица на последнем месте».

Новое в Python 3.9.

Смотрите также математическую функцию math.nextafter().

Курс по Python: https://stepik.org/course/100707

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

Но, вначале пару
слов о самом алгоритме Евклида, о принципе его работы. Сначала рассмотрим его
медленный, но простой вариант.

Например, пусть
даны два натуральных числа: a = 18 и b = 24. Чтобы
определить для них НОД, будем действовать, следующим образом. Из большего
значения вычтем меньшее и результат сохраним в переменной с большим значением,
то есть, в b. Фактически,
это означает, что мы выполняем операцию: b = b — a. Теперь у нас
два значения a = 18, b = 6. Для них
повторяем тот же самый процесс. Здесь большее уже переменная a, поэтому,
корректируем ее значение, вычитая меньшее. Получаем новую пару a = 12, b = 6. Опять
повторяем этот процесс и видим, что a = 6, b = 6 –
переменные равны. В этом случае останавливаем алгоритм и получаем, что НОД(18,
24) = 6, что, в общем то, верно.

Весь этот
алгоритм можно представить следующим псевдокодом:

Давайте его
опишем с помощью, следующей функции:

def get_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
 
    return a

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

Выполним эту
функцию со значениями аргументов 18 и 24:

res = get_nod(18, 24)
print(res)

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

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

После того, как
функция определена, ее следует протестировать и убедиться в корректности
возвращаемых результатов. Для этого тестировщик создает свою вспомогательную
функцию. Используя наши текущие знания, мы ее опишем, следующим образом:

def test_nod(func):
    # -- тест №1 -------------------------------
    a = 28
    b = 35
    res = func(a, b)
    if res == 7:
        print("#test1 - ok")
    else:
        print("#test1 - fail")
 
    # -- тест №2 -------------------------------
    a = 100
    b = 1
    res = func(a, b)
    if res == 1:
        print("#test2 - ok")
    else:
        print("#test2 - fail")
 
    # -- тест №3 -------------------------------
    a = 2
    b = 10000000
 
    st = time.time()
    res = func(a, b)
    et = time.time()
    dt = et - st
    if res == 2 and dt < 1:
        print("#test3 - ok")
    else:
        print("#test3 - fail")

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

Далее, выполним
импорт нужного нам модуля time для вызова
функции time():

и в конце вызовем
тестирующую функцию для тестирования get_nod:

Смотрите, у нас
первые два теста прошли, а третий – не прошел, так как функция слишком долго
вычисляла результат.

Давайте поправим
ее и ускорим алгоритм Евклида. Как это можно сделать? Смотрите, если взять два
числа a = 2 и b = 100, то по
изначальному алгоритму мы будем делать многочисленные вычитания из b a, пока значения
не сравняются. То есть, мы здесь, фактически, вычисляем остаток от вхождения
двойки в сотню, а это есть не что иное, как операция:

b = b % a = 0

И никаких
циклических вычитаний! Это, очевидно, будет работать много быстрее. При этом,
как только получаем остаток равный нулю, то НОД – это значение меньшей
переменной, то есть, в нашем примере – a = 2.

То же самое для
предыдущих значений a = 18, b = 24. Получаем серию таких
вычислений:

b = 24 % 18 = 6

a = 18 % 6 = 0

Значит, НОД(18,
24) = 6. Видите, как это быстро и просто! На уровне псевдокода быстрый алгоритм
Евклида можно описать так:

пока
меньшее число больше 0

        
большему числу присваиваем остаток от деления на меньшее число

выводим большее
число

Реализуем его в
виде функции:

def get_fast_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по быстрому алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    if a < b:
        a, b = b, a
 
    while b != 0:
        a, b = b, a % b
 
    return a

Предлагаю, в
качестве самостоятельного задания, вам самим в деталях разобраться, как она
работает. А мы ее сразу протестируем:

Как видите, она
проходит все три наших теста.

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

Курс по Python: https://stepik.org/course/100707

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

Для начала разберемся, что это и как это работает. Алгоритм Евклида позволяет найти нам наибольший общий делитель чисел. Как это работает:
Пусть a = 18, b = 30.
Цикл: a!=0 and b!=0
Если a > b, то a = a % b, если меньше, то b = b % a, таким образом мы сначала находим остаток деления, а потом повторяем действия. У нас a < b, значит, ищем остаток деления b % a (30 % 18) = 12, присваиваем b = 12, повторяем цикл но теперь у нас уже a > b(b = 12)
значит выполняем a % b (18 % 12) = 6? снова переходим к циклу, теперь снова b > a, значит выполняем b % a (30 % 6), остаток от деления 0, на этом мы прекращаем наш цикл и узнаем, что наибольший общий делитель 18 и 30 = 6. и выводим a + b (b = 0, a = 6).

Python

#!/usr/bin/env python
a = 18
b = 30
 
while a!=0 and b!=0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print (a+b)

Perl:

 sub nod
 {
 return  $_[0] != 0  ?  nod ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
 }

C:

 int gcd(int a, int b) {
   int c;
   while (b) {
      c = a % b;
      a = b;
      b = c;        
   }
   return abs(a);
 }

Pascal:

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   nod:= a + b;
  end;

Java:

public class GCD {
    public static int gcd(int a,int b) {
        while (b !=0) {
            int tmp = a%b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

C#:

int gcd(int a, int b)
{
    while (b != 0)
        b = a % (a = b);
    return a;
}