-
Notifications
You must be signed in to change notification settings - Fork 0
/
GCD & LCM Python
41 lines (34 loc) · 1.07 KB
/
GCD & LCM Python
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from sys import stdin
def find_gcd(a: int, b: int) -> int:
"""
complexity: O(log min(a,b))
--- recursion, Euclid algorithm ---
calculates the greatest common divisor (gcd) of 2 numbers - a and b
! a should be bigger than b (a > b) for better production !
:param a: first (bigger) number
:param b: second(less) number
:return: gcd
"""
if not a and not b:
return "∞"
while b != 0:
a %= b
a,b = b,a
return a
def find_lcm(a,b):
"""
--- recursion, Euclid algorithm ---
calculates the least common multiplier (lcm) of 2 numbers - a and b
! a should be bigger than b (a > b) for better production !
:param a: first (bigger) number
:param b: second(less) number
:return: lcm
"""
try:
return a // find_gcd(a,b) * b
except (TypeError, ZeroDivisionError):
return None
if __name__ == "__main__":
while 1:
n, k = map(int, stdin.readline().split())
print("gcd: {gcd} lcm: {lcm}".format(gcd=find_gcd(n,k), lcm=find_lcm(n,k)))