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

1. 최대공약수 구하기

 

- 두 개의 자연수에 대한 최대공약수를 구하는 유클리드 호제법 알고리즘 이용한다.

- 유클리드 호제법

   ->두 자연수 a, b에 대하여(a > b) a를 b로 나눈 나머지를 R이라 하면, a와 b의 최대공약수는 b와 R의 최대공약수와 같다.

- 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성

 

 

 

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
print(gcd(192, 162))

 

2. 최소공배수 구하기

 

- 서로 다른 수 a, b의 배수중에서 공통되는 배수 중에 가장 작은 값을 의미한다.

- 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 된다.

 

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