유클리드 호제법(최대공약수)

유클리드 호제법은 두 수의 최대공약수(GCD)를 빠르게 구하는 방법이다. 핵심은 “큰 수를 작은 수로 나눈 나머지로 계속 바꿔가면 된다”는 것 하나다.

원리

두 수 a, b (a > b)에 대해
gcd(a, b) = gcd(b, a % b)

즉, 큰 수를 작은 수로 나눈 나머지로 계속 바꿔도 최대공약수는 변하지 않는다.

코드 (JS 기준)

function gcd(a, b) {
  while (b !== 0) {
    let temp = a % b;
    a = b;
    b = temp;
  }
  return a;
}

시간 복잡도

• 단순히 약수 다 구하는 방식 → O(n)
• 유클리드 호제법 → O(log n)

숫자가 커질수록 압도적으로 빠르다.

최소공배수 구하는 법

lcm = (a / gcd(a, b)) * b;

이렇게 미리 나눠줘야 오버플로우를 방지할 수 있다.