1602. LCM of two integers

Find the LCM (least common multiple) of two positive integers.

Input. Two positive integers a and b (a, b ≤ 2 * 10⁹).

Output. Print the LCM of numbers a and b.

Sample input	Sample output
42 24	168

SOLUTION

LCM

Algorithm analysis

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:

GCD (a, b) * LCM (a, b) = a * b,

therefore

LCM (a, b) = a * b / GCD (a, b)

Since a, b < 2 * 10⁹, the result of multiplying a * 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:

GCD (42, 24) * LCM (42, 24) = 42 * 24,

thus

LCM (42, 24) = 42 * 24 / GCD (42, 24) = 42 * 24 / 6 = 168

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))