НСК двох натуральних чисел#1602

НСК двох натуральних чисел (Розбір)

Найменше спільне кратне (НСK) двох цілих чисел $a$ і $b$ називається найменше натуральне число, яке ділиться націло на $a$ і на $b$ . Наприклад, $НС K (2, 3) = 6$ НСK(2, 3) = 6, $НС K (6, 10) = 30$ НСK(6, 10) = 30.

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

НСД (a, b) \cdot НС K (a, b) = a \cdot b,

НСД(a, b) \cdot НСK(a, b) = a \cdot b,

звідки

НС K (a, b) = \frac{a \cdot b}{НСД ( a , b )}

НСK(a, b) = \frac{a \cdot b}{НСД(a, b)}

Оскільки $a, b < 2 \cdot 1 0^{9}$ a, b < 2 \cdot 10^9, то при множенні значення $a \cdot b$ a \cdot b може вийти за межі типу int. При обчисленні слід скористатися типом long long.

Приклад

Розглянемо числа з прикладу:

НОД (42, 24) \cdot НС K (42, 24) = 42 \cdot 24,

НОД(42, 24) \cdot НСK(42, 24) = 42 \cdot 24,

звідки

НС K (42, 24) = \frac{42 \cdot 24}{НОД ( 42 , 24 )} = \frac{42 \cdot 24}{6} = 168

НСK(42, 24) = \frac{42 \cdot 24}{НОД(42, 24)} = \frac{42 \cdot 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;
}

C++

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо НСK двох чисел.

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

Python

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо НСK двох чисел.

print(lcm(a, b))

Python реалізація — lcm

Для обчислення найменшого спільного кратного (НСK) двох чисел скористаємося функцією lcm, вбудованою в мові Пітон.

import math

Читаємо вхідні дані.

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

Обчислюємо і виводимо НСK двох чисел.

print(math.lcm(a, b))