-
Notifications
You must be signed in to change notification settings - Fork 1
/
lcm.py
26 lines (19 loc) · 717 Bytes
/
lcm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Least Common Multiple
# Author: jerrybelmonte
# Input: Two integers a and b seperated by a space.
# Output: Least common multiple of a and b.
# Uses the Euclidean algorithm of the greatest common divisor
# to compute the least common multiple.
def lcm(a, b):
# greatest common divisor helper function
def gcd(a, b):
left, right = max(a, b), min(a, b)
if right == 0: # base case
return left # left is the greatest common divisor
# recursively call the gcd function
return gcd(right, (left % right))
# return the least common multiple
return (a // gcd(a, b)) * b
if __name__ == '__main__':
a, b = input().split()
print(lcm(int(a), int(b)))