Как найти наименьшее общее кратное двух чисел python

Наименьшее общее кратное

где a и b — это натуральные числа, НОД — наибольший общий делитель.

Решение задачи на языке программирования Python

Из условия задачи ясно, чтобы найти НОК, надо сначала найти НОД. Последний можно вычислить, постепенно находя остаток от деления большего числа из пары на меньшее и присваивая остаток переменной, связанной с большим числом (см. алгоритм Евклида). В какой-то момент значение одной из переменных станет равным 0. Когда это произойдет, другая будет содержать НОД. Если неизвестно, какая именно переменная содержит НОД, то можно просто сложить значения обоих переменных.

В коде ниже используется функция для нахождения НОК, которая принимает два числа и возвращает найденное наименьшее общее кратное.

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

def lcm(a, b): m = a * b while a != 0 and b != 0: if a > b: a %= b else: b %= a return m // (a + b) while 1: try: x = int(input('a = ')) y = int(input('b = ')) print('НОК:', lcm(x, y)) except ValueError: break

a = 14 b = 18 НОК: 126 a = 105 b = 305 НОК: 6405 a = stop

В модуле math языка программирования Python есть функция для нахождения наибольшего общего делителя ( gcd — greatest common devisor). При ее использовании наша функция вычисления наименьшего общего кратного lcm (least common multiple) упрощается.

def lcm(a, b): import math return (a * b) // math.gcd(a, b)

X Скрыть Наверх

Решение задач на Python

Нахождение наименьшего общего кратного (НОК) при помощи рекурсии

Программа принимает на вход два числа и находит наименьшее общее кратное (НОК) при помощи рекурсии.

Решение задачи

1. Принимаем два числа и записываем их в отдельные переменные.
2. Вводим переменную, которая в начале работы функции принимает значение наибольшей из двух переменных.
3. Проверяем, делится ли без остатка число, содержащееся во вновь введенной переменной, на оба данных нам числа одновременно.
4. Если делится, то функция прекращает свою работу и выводит это число, которое и будет наименьшим общим кратным (НОК).
5. Если нет, то опять вызывается эта рекурсивная функция, в которой значение переменной еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа.
6. После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.

Исходный код

Ниже дан исходный код, который осуществляет нахождение наименьшего общего кратного (НОК) с использованием рекурсии. Результаты работы программы также даны ниже.

def lcm(a, b): lcm.multiple = lcm.multiple + b if ((lcm.multiple % a == 0) and (lcm.multiple % b == 0)): return lcm.multiple; else: lcm(a, b) return lcm.multiple lcm.multiple = 0 a = int(input("Введите первое число:")) b = int(input("Введите второе число:")) if (a > b): LCM = lcm(b, a) else: LCM = lcm(a, b) print("НОК:") print(LCM)

Объяснение работы программы

1. Пользователь вводит два числа и они записываются в переменные a и b .
2. Также вводится еще одна переменная, lcm.multiple , которая для начала инициируется нулем.
3. Далее проверяется, какое из введенных чисел больше, чтобы передать их в рекурсивную функцию lcm() в порядке возрастания.
4. В функции lcm() на первом шаге значение переменной увеличивается на величину наибольшего из введенных пользователем чисел. То есть при первом вызове функции значение переменной становится равным этому числу.
5. Затем происходит проверка, делится ли значение переменной lcm.multiple без остатка на оба наших числа одновременно. Если делится, то функция прекращает свою работу и выводит в качестве результата значение переменной lcm.multiple .
6. Если нет, то опять вызывается рекурсивная функция lcm() , в которой значение переменной lcm.multiple еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа.
7. После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.

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

Пример 1: Введите первое число:126 Введите второе число:12 НОК: 252 Пример 2: Введите первое число:25 Введите второе число:5 НОК: 25

Нахождение НОК и НОД в Python — примеры

В данном уроке мы узнаем, как найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) с помощью языка программирования Python.

Но прежде чем мы начнем, давайте разберем, что обозначает Least Common Multiple (LCM) — наименьшее общее кратное.

НОК: наименьшее общее кратное

Это понятие арифметики и системы счисления. НОК двух целых чисел a и b обозначается НОК(a,b). Это наименьшее натуральное число, которое делится и на «а», и на «b».

Например: у нас есть два целых числа 4 и 6. Найдем НОК:

4, 8, 12, 16, 20, 24, 28, 32, 36. and so on.

• Кратные 6:

6, 12, 18, 24, 30, 36, 42. and so on.

Общие кратные 4 и 6 — это просто числа, которые есть в обоих списках:

12, 24, 36, 48, 60, 72. and so on.

НОК — это наименьший общий множитель, поэтому он равен 12.

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

# defining a function to calculate LCM def calculate_lcm(x, y): # selecting the greater number if x > y: greater = x else: greater = y while(True): if((greater % x == 0) and(greater % y == 0)): lcm = greater break greater += 1 return lcm # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The L.C.M. of", num1,"and", num2,"is", calculate_lcm(num1, num2))

Enter first number: 3 Enter second number: 4 The L.C.M. of 3 and 4 is 12

Эта программа сохраняет два числа в num1 и num2 соответственно. Эти числа передаются в функцию calculate_lcm(). Функция возвращает НОК двух чисел.

Внутри функции мы сначала определили большее из двух чисел, поскольку наименьшее общее кратное может быть больше или равно наибольшему числу. Затем мы используем бесконечный цикл while, чтобы перейти от этого числа и дальше.

На каждой итерации мы проверяли, идеально ли делят оба числа число. Если это так, мы сохранили число как НОК и вышли из цикла. В противном случае число увеличивается на 1, и цикл продолжается.

НОД: наибольший общий делитель

В этом разделе мы разберем, как найти Highest Common Factor (HCF) — наибольший общий делитель (НОД) в языке программирования Python.

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

У нас есть два целых числа 8 и 12. Найдем наибольший общий делитель.

• Делители числа 8:

1, 2, 4, 8

• Делители числа 12:

1, 2, 3, 4, 6, 12

НОД 8 и 12 равны 4.

Теперь давайте рассмотрим пример, основанный на нахождении НОД двух заданных чисел.

# defining a function to calculate HCF def calculate_hcf(x, y): # selecting the smaller number if x > y: smaller = y else: smaller = x for i in range(1,smaller + 1): if((x % i == 0) and(y % i == 0)): hcf = i return hcf # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The H.C.F. of", num1,"and", num2,"is", calculate_hcf(num1, num2))

Enter first number: 8 Enter second number: 12 The H.C.F. of 8 and 12 is 4

В приведенном выше фрагменте кода два целых числа, хранящиеся в переменных num1 и num2, передаются в функцию calculate_hcf(). Функция вычисляет НОД для этих двух чисел и возвращает его.

Внутри функции мы должны определить меньшее число, поскольку НОД может быть меньше или равен наименьшему числу. Затем мы использовали цикл for, чтобы перейти от 1 к этому числу.

На каждой итерации мы должны проверять, точно ли число делит оба входных числа. Если это так, мы должны сохранить число как НОД. По завершении цикла мы получаем наибольшее число, которое идеально делит оба числа.

Наименьшее общее кратное

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

# Наименьшее общее кратное двух чисел - # это наименьшее число, # которое делится нацело на оба заданных числа. def lcm(a, b): # Произведение всегда кратно # любому из своих множителей. m = a * b # Однако оно может быть # не наименьшим общим кратным. # поиск наибольшего общего делителя while a != 0 and b != 0: if a > b: a = a % b else: b = b % a # Наименьшее общее кратное вычисляется # с помощью деления произведения чисел # на их наибольший общий делитель. # Здесь используется целочисленное деление # только потому, что Python # при обычном делении (/) # всегда возвращает тип float. return m // (a + b) x = int(input('a=')) y = int(input('b=')) print('LCM:', lcm(x, y))

Похожие записи:

1. Эффективный ввод-вывод в разных языках программирования
2. Django — доработка шаблона формы регистрации
3. Django — объект формы и Generic Views
4. Найти квадратные уравнения, которые имеют решения в указанных диапазонах коэффициентов