Editorial

The Least Common Multiple (LCM) of two integers $a$ and $b$ is the smallest positive integer divisible by both $a$ and $b$ without a remainder. For example, $LCM(2,3)=6$ and $LCM(6,10)=30$.

To find the least common multiple, we can use the formula:

therefore

Since $a,b<2\cdot 10^9$, the result of multiplying $a\cdot b$ may exceed the range of the int type. Therefore, when performing calculations, it is advisable to use the long long type.

Example

Let’s consider the numbers from the example:

thus

Algorithm implementation

Implement the functions gcd (greatest common divisor) and lcm (least common multiple).

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;
}

The main part of the program. Read the input data.

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

Compute and print the LCM of two numbers.

d = lcm(a, b);
printf("%lld\n", d);

Python implementation

Implement the functions gcd (greatest common divisor) and lcm (least common multiple).

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

The main part of the program. Read the input data.

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

Compute and print the LCM of two numbers.

print(lcm(a, b))

Python implementation — lcm

To compute the least common multiple (LCM) of two numbers, let's use the lcm function built into the Python language.

import math

Read the input data.

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

Compute and print the LCM of two numbers.

print(math.lcm(a, b))