1602. НОК двух натуральных чисел

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

Вход. Два натуральных числа a и b (a, b ≤ 2 * 10⁹).

Выход. Выведите НОК чисел a и b.

Пример входа	Пример выхода
42 24	168

РЕШЕНИЕ

НОК

Анализ алгоритма

Наименьшим общим кратным (НОК) двух целых чисел a и b называется наименьшее натуральное число, которое делится нацело на a и на b. Например, НОК (2, 3) = 6, НОК (6, 10) = 30.

Для нахождения наименьшего общего кратного воспользуемся формулой:

НОД(a, b) * НОК(a, b) = a * b

Откуда

НОК(a, b) = a * b / НОД(a, b)

Поскольку a, b < 2 * 10⁹, то при умножении значение a * b может выйти за пределы типа int. При вычислении следует воспользоваться типом long long.

Пример

Рассмотрим числа из примера:

НОД(42, 24) * НОК(42, 24) = 42 * 24,

откуда

НОК(42, 24) = 42 * 24 / НОД(42, 24) = 42 * 24 / 6 = 168

Реализация алгоритма

Реализуем функции gcd (наибольший общий делитель) и lcm (наименьшее общее кратное).

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b, a % b);

}

long long lcm(long long a, long long b)

{

return a / gcd(a, b) * b;

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld", &a, &b);

Вычисляем и выводим НОК двух чисел.

d = lcm(a, b);

printf("%lld\n", d);

Python реализация

Реализуем функции gcd (наибольший общий делитель) и lcm (наименьшее общее кратное).

def gcd(a, b):
 if a == 0: return b
 if b == 0: return a
 if a > b: return gcd(a % b, b)
 return gcd(a, b % a)
 
def lcm(a, b):
 return a // gcd(a, b) * b
 

Основная часть программы. Читаем входные данные.

 
a, b = map(int, input().split())
 

Вычисляем и выводим НОК двух чисел.

 
print(lcm(a, b))
 

Python реализация – lcm

Для вычисления наименьшего общего кратного (НОК) двух чисел воспользуемся функцией lcm, встроенной в языке Питон.
 
import math
 
Читаем входные данные.
 
a, b = map(int, input().split())
 

Вычисляем и выводим НОК двух чисел.

 
print(math.lcm(a, b))