유클리드 호제법 (최대공약수, 최소공배수 구하는법)

유클리드 호제법

두 수 a,b의 최대공약수는 a와 b를 나눈 나머지 r의 최대 공약수와 같다.

GCD(a,b) = GCD(b,r)

나머지 r이 0이 될 때, 그 때의 b가 a와 b의 최대공약수가 된다.

---

유클리드 호제법의 과정

r = a%b
r !== 0 => a=b, b=r로 설정후 반복

---

유클리드 호제법을 이용해 최소공배수 구하기

a*b/GCD(a,b)

function gcdlcm(a, b) {
  let ab = a * b;
  while (b !== 0) {
    let remainder = a % b;
    (a = b), (b = remainder);
  }
  return [a, ab / a];
}

//[4,24]