[Algorithm] 유클리드 호제법(최대공약수, 최소공배수)

1. 유클리드 호제법

: 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘

 

큰 수들의 최대공약수를 구할때 사용할 수 있습니다. 최소공배수도 응용을 거쳐 구할 수 있습니다.

 

2개의 자연수 a, b가 있을 때 a를 b로 나눈 나머지를 r이라 할때 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

단 (a > b)이어야 합니다.

 

과정을 b가 양수일때까지 반복하고 마지막의 a값이 최대공약수가 됩니다.

 

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

 

리턴 값 a가 최대공약수

 

2. 최소공배수

 

A와 B의 곱을 최대공약수로 나누어주면 최소공배수가 됩니다.

 

그래서 최소공배수를 구하기 위해선 최대공약수를 구하는 함수를 미리 만들어 놓는것이 좋습니다.

 

A와 B의 최대공약수를 G라 하고 그에 따른 서로소를 a, b라 할때 A = aG, B = bG라고 할 수 있고 AB = abG²가 됩니다.

 

따라서 AB / G = abG 라고 할 수 있습니다.

 

이 공식을 리턴문 옆에 고스란히 적어주면 lcm구하는 함수가 됩니다.

 

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

 

정수를 얻기 위해 //로 해주었습니다.

 

예시)