최대공약수와 최소공배수의 관계 (유클리드 호제법)

유클리느 호제법이란?

https://velog.io/@yerin4847/W1-유클리드-호제법

유클리드 호제법(Euclidean-algorithm)

개념은 정리가 너무 잘 되어있어 링크째로 남긴다.

 

최대공약수(GCD, Greatest Common Divisor)

코드

위 포스팅 예제는 C언어로 작성되었기 때문에 파이썬으로 나타내봤다.

 

반복문

# 반복분
def gcd(a, b):
  while b:
    temp = a % b
    a = b
    b = temp
  return a

재귀함수

# 재귀함수
def gcd(a, b):
  return (gcd(b, a % b) if b else a)

 

최소공배수(LCM, Least Common Multiple)

두 수 a, b에 대해 위 방법을 통해 최대공약수를 구한 뒤

두 수의 곱을 나누면 된다.

코드

def lcm(a, b):
  return a * b / gcd(a, b)