Наименьшее общее кратное (НОК / LCM)

В этом примере посмотрим, как найти наименьшее общее кратное (НОК, в английской традиции — LCM) двух чисел на Python. Покажем два способа: простой перебор и более быстрый — через НОД (наибольший общий делитель).

Что нужно знать

Перед изучением примера полезно понимать:

Примечание

Наименьшее общее кратное двух чисел — это наименьшее положительное целое число, которое делится без остатка на оба исходных числа. Например, НОК 12 и 14 равен 84.

Пример 1. Простой перебор

# Python Program to find the L.C.M. of two input number

def compute_lcm(x, y):

   # choose 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

num1 = 54
num2 = 24

print("The L.C.M. is", compute_lcm(num1, num2))

Вывод

The L.C.M. is 216

Совет

Чтобы проверить программу на других значениях, меняй num1 и num2.

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

Сначала находим большее из двух чисел: НОК не может быть меньше, чем самое большое из них. Затем запускаем бесконечный цикл while от этого числа и выше.

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

Этот способ работает медленно. Его можно сильно ускорить, если воспользоваться известным фактом: произведение двух чисел равно произведению их НОК и НОД.

Number1 * Number2 = L.C.M. * G.C.D.

Ниже — программа, которая использует это соотношение.

Пример 2. Через НОД

# Python program to find the L.C.M. of two input number

# This function computes GCD
def compute_gcd(x, y):

   while(y):
       x, y = y, x % y
   return x

# This function computes LCM
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

num1 = 54
num2 = 24

print("The L.C.M. is", compute_lcm(num1, num2))

Результат тот же. В программе две функции: compute_gcd() и compute_lcm(). Чтобы посчитать НОК, нужен НОД, поэтому compute_lcm() вызывает compute_gcd(). Сам НОД считается алгоритмом Евклида — это быстро и эффективно.