[알고리즘] 최대공약수(GCD) 계산 알고리즘 : 유클리드 호제법

✨ 최대공약수 GCD

큰 수에서 작은 수를 빼는 연산을 한 쪽이 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)

---

✅ 최소공배수 LCM

최소 공배수 : 최대 공약수 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