최대공약수, 최소공배수 구하기

A, B의 최대공약수는 B, A%B의 최대공약수와 같다.

 

이 성질을 이용해 A%B의 결과가 0이 될 때까지 나머지를 구해주면

 

최대 공약수를 얻을 수 있다.

 

아래는 최대 공약수를 구하는 함수이다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
 
a = gcd(n, m)
b = (n*m) // a

 

최소공배수는 최대공약수를 알고 있다면 쉽게 구할 수 있다.

 

'A x B = 최대공약수 x 최소공배수'이기 때문에

 

'최소공배수 = A x B / 최대공약수'로, A와 B를 곱한 값에서 최대공약수를 나눠주면 된다.