СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ И НАИМЕНЬШЕГО ОБЩЕГО КРАТНОГО В PYTHON
СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ И НАИМЕНЬШЕГО ОБЩЕГО КРАТНОГО В PYTHON
Рустамова Нигина Бобир кизи
студент, Бухaрский гoсудaрственный университет,
Республика Узбекистaн, г. Бухaрa
Рустамов Хаким Шарипович
доц., Бухарский государственный университет,
Республика Узбекистaн, г. Бухaрa
АННОТАЦИЯ
В этой статье обсуждается трудоемкий процесс вычисления наибольшего общего делителя и наименьшего общего кратного с использованием языка программирования Python.
Ключевые слова: вводимая информация, Time- модуль для работы с временем, наибольший общий делитель, наибольшее общее кратное.
Вычисление НОД (наибольшего общего делителя), о котором мы узнали в начальной школе, помогает сократить дроби. Наибольшим общим делителем двух чисел a и b называется наибольшее число, на которое a и b делятся без остатка. Для записи может использоваться аббревиатура НОД. Для двух чисел можно записать вот так: НОД (a, b). Например, для 4 и 16 НОД будет 4.[1]
А вычисление НОК (наименьшее общее кратное), помогает найти общий знаменатель для данных дробей. Наименьшее общее кратное (НОК) чисел – это наименьшее число, которое можно поделить на каждое из этих чисел без остатка.
Правило нахождения НОК нескольких чисел:
1.Разложить данные числа на простые множители.
2.Выписать все простые числа, которые входят хотя бы в одно из полученных разложений.
3.Каждое из выписанных простых чисел взять с наибольшим из показателей степени, с которыми оно входит в разложения данных чисел.
4.Записать произведение полученных степеней.[2]
Первый способ
Евклид в III веке до нашей эры описал алгоритм для нахождения наибольшего общего делителя. Его способ заключается следующим образом: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем[3]. Если не делится то сохраняем остаток и минимальное число которое заданно, делим на этот остаток.
Теперь перейдем к коду для автоматизации всего алгоритма.
import time
a,b=map(int,input().split())
begin=time.time()
while a!=0 and b!=0:
if a>b:
a=a%b
else:
b=b%a
result=a+b
print('НОД двух чисел равно '+str(result))
finish=time.time()
print(finish-begin)
Входные данные:
36 96
Выходные данные:
НОД двух чисел равно 12
0.015588998794555664
Время, которое потребовалось для запуска первой программы
0.015588998794555664
Второй способ
Второй способ похожа на первый но тут мы вычисляем разность. Если число а больше чем b, то b-a, иначе a-b, цикл продолжается до тех пор, пока число a не равняется с числом b.
import time
a,b=map(int,input().split())
begin=time.time()
a1=a #сохраняем числы, чтобы они не потерялись во время ввода кода
b1=b
while a!=b:
if a>b:
a=a-b
else:
b=b-a
result=b
print( 'НОД двух чисел '+str(a1)+' и '+str(b1)+' равно '+str(result))
finish=time.time()
print(finish-begin)
Входные данные:
36 96
Выходные данные:
НОД двух чисел 36 и 96 равно 12
0.0030181407928466797
Время, которое потребовалось для запуска второй программы
0.0030181407928466797
Теперь перейдем к поиску НОК по коду. Здесь мы можем использовать алгоритм Евклида.
Пример: Наименьшим общим кратным чисел 3, 4 и 9 является число 36, никакое другое число меньше 36 не делится одновременно на 3, 4 и 9 без остатка. [4]
Функция НОК используется для сложения и вычитания дробей с разными знаменателями. Как наибольший общий делитель может быть связан с наименьшим общим кратным?
Эта связь между НОД и НОК определяется следующей теоремой.
Теорема. Наименьшее общее кратное двух положительных целых чисел a и b равно произведению чисел a и b, деленному на наибольший общий делитель чисел a и b, то есть, НОК(a, b)=a·b:НОД(a, b).[5]
Чтобы найти НОК, мы используем в коде следующую теорему, таким образом мы упрощаем дело, то есть добавляем эту формулу в код которой вычисляющий НОД. Наш код будет похож на код, вычисляющий НОД, но с небольшим отличием.
Первый способ
import time
a,b=map(int,input().split()) #номера которые вы указали
begin=time.time()
a1=a #сохраняем числы, чтобы они не потерялись во время ввода кода
b1=b
c=a*b
while a!=b:
if a>b:
a=a-b
else:
b=b-a
result=b
print( 'НОК двух чисел '+str(a1)+' и '+str(b1)+' равно '+str(c//result))
finish=time.time()
print(finish-begin)
Входные данные:
12345 56778
Выходные данные:
НОК двух чисел 12345 и 56778 равно 233641470
0.005243778228759766
Время, которое потребовалось для запуска второй программы
0.005243778228759766
Второй способ
import time
a,b=map(int,input().split()) #номера которые вы указали
begin=time.time()
a1=a #сохраняем числы, чтобы они не потерялись во время ввода кода
b1=b
c=a*b
while a!=0 and b!=0:
if a>b:
a=a%b
else:
b=b%a
result=b+a
print( 'НОК двух чисел '+str(a1)+' и '+str(b1)+' равно '+str(c//result))
finish=time.time()
print(finish-begin)
Входные данные:
12345 56778
Выходные данные:
НОК двух чисел 12345 и 56778 равно 233641470
0.0066950321197509766
Третий способ
Конечно, вы можете создать алгоритм, который вычисляет только НОК. Но это может занять больше времени, чем предыдущие коды. Давайте попробуем это сделать.
import time
a,b=map(int,input().split())
begin=time.time()
c=a*b
mx=max(a,b)
for i in range(mx,c+1):
if i%a==0 and i%b==0:
print(i)
break
finish=time.time()
print(finish-begin)
Входные данные:
12345 56778
Выходные данные:
233641470
88.16556096076965
Вывод
Лучший способ найти НОД — второй способ. Потому что он делает свою работу быстрее, чем первый.
Оптимальный способ найти НОК — первый способ. Потому что он делает свою работу быстрее, чем других.
Список литературы:
- A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, 1st ed., Addison-Wesley, Boston
- Вагутен В.Н. Алгоритм Евклида и основная теорема арифметики. –Журнал «Квант», 1972, №2, стр. 30-35.