유클리드 호제법

호제법이라는 말이 두 수를 서로 나눠보면서 원하는 수를 얻어간다는 뜻이다.

유클리드 호제법은 최대공약수(gcd)를 구하는 알고리즘으로 

두 수 a,b(a>=b) 일 때

gcd(a,b) { return b?gcd(b,a%b):a ; } 로 구현할 수 있다.

 

최대공약수 얘기를 한 겸 최소공배수(lcm)도 같이 얘기해야겠다.

최소공배수는 두 수 a, b 가 모두 가지는 배수의 최소값을 말한다.

최대공약수와 최소공배수의 관계에 따라 다음과 같이 구현할 수 있다.

lcm(a,b) { return a*b/gcd(a,b); }

두 수의 곱을 최대공약수로 나눈 값이 최소공배수 이다.