최대공약수 최소공배수 알고리즘 (유클리드 호제법)

최대공약수

➡️유클리드 호제: 2 개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

 두 수를 입력으로 받고 작은 수가 0이 될때 까지 나누기 

def gcd(a, b):
  while (b != 0):
    r = a % b
    a = b
    b = r
  
  return a

최소공배수

두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

def lcm(a, b):
  return (a * b) / gcd(a, b)
def gcd(a, b):
  while (b != 0):
    r = a % b
    a = b
    b = r
  
  return a