유클리드 호제법

호제법이란 두 수가 상대방 수를 나눠서 원하는 수를 얻는 알고리즘을 말한다.
최소공배수와 최대공약수를 유클리드 호제법으로 구현한 알고리즘을 많이 사용하기에 정리해보려 한다.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 s라고 하면(a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

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

반대로 최소공배수는 a,b의 곱을 a,b의 최대공약수로 나누면 나온다.
(최소공배수 x 최대 공약수) = gcd^2 a b [a, b은 서로수] => a * b
를 이용한 방법이다

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