큰 수에서 작은 수를 빼는 연산을 한 쪽이 0이 될 때까지 반복하여 남는 숫자가 gcd가 된다.
def gcd_mod(a, b):
while a * b != 0:
if a > b:
a %= b
else:
b %= a
return a + b
# 재귀함수로 구현
def gcd_rec(a, b):
if a % b == 0:
return b
return gcd_rec(b, a%b)
최소 공배수 : 최대 공약수 G, 서로소 x, y가 있을 때 G G x * y / G로 구할 수 있다.
- G G x y = a b
- lcm = a * b // G
def lcm(a, b): lcm = (a * b) // gcd(a, b) return lcm