유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기 (python)

유클리드 호제법

최대공약수를 구하기 위해 사용할 때 쓰는 방법이다.

a > b 인 두 수가 있을 때, a를 b로 나눈 나머지는 r이라고 해보자.
이때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 것을 이용한다.

위 내용을 기반으로 계속 반복하면 실질적인 a, b의 최대공약수를 구할 수 있다는 것이다.
예시로 44와 33이 있다고 해보면,
1. a = 44, b = 33, r = 11 => b와 r의 최대약수를 구하기.
2. a = 33, b = 11, r = 0 => 나머지가 0이므로 b가 최대공약수가 된다.

이러한 방법으로 python 코드로 최대공약수와 최소공배수를 구성해 보자.

최대공약수 및 최소공배수

최대공약수

보통의 경우 아래 최대 공약수 함수는 주어지는 값 a, b가 있을 때 a가 b보다 항상 크거나 같다고 가정하에 아래처럼 사용할 수 있다.

def gcd(a,b):
	for i in range(b, 0, -1):
    	if a % i == 0 and b % i == 0:
        	return i

유클리드 호제법을 이용하면 아래와 같이 사용 가능하다.

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

최소공배수

아래 최소 공배수 함수는 주어지는 값 a, b가 있을 때 a가 b보다 항상 크거나 같다고 가정하에 아래처럼 사용할 수 있다.

def lcm(a,b)
    for j  in range(a, a*b+1):
        if j % a == 0 and j % b == 0:
            return j

이러한 방법 말고, 최소공배수의 성질인

a * b = 최소공배수 * 최대공약수

를 이용해, 앞서 구한 최대공약수 함수를 이용해서 최소 공배수를 손쉽게 풀이할 수 있다.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# 최소공배수
def lcm(a, b):
    return a * b // gcd(a, b)