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

괄괄이·2023년 10월 15일
0

알고리즘 이론

목록 보기
9/9

✨ 최대공약수 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

0개의 댓글