[알고리즘] 유클리드 호제법

최대 공약수

1. a,b (단, a>b)가 있다.
2. a 를 b로 나웠을 때, 나머지(r)가 0인지 확인한다.
3. 나머지(r) 0이 아니라면 a에 b를 넣고, b에는 r을 넣어서 2번 과정을 진행한다.
4. 만약 나머지(r)이 0이라면 그 때의 b가 최대 공약수가 된다.

function gcd(a,b) {
  let r = a % b;
  return r ? gcd(b,r) : b;
}

최소 공배수

최소 공배수 * 최대공약수 = 0이 아닌 두 수의 곱임을 이용

=> 최소 공배수 = 0이 아닌 두 수의 곱 / 최대 공약수

function gcd(a,b) {
  let r = a % b;
  return r ? gcd(b,r) : b;
}

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