[Algorithm] 유클리드 호제법

유클리드 호제법이란?

2개의 자연수의 최대공약수를 구할 수 있는 공식으로 명시적으로 기술된 가장 오래된 알고리즘이다.

호제법(互除法)이란 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻어낸다는 의미이다.

 

정리

두 수 a, b가 있다고 가정해보자. (a > b)

큰 수(a)를 작은 수(b)로 나눴을 때 나머지 값이 0이 되면, 나눴던 수 중 작은 수(b)가 최대공약수가 된다.

0이 되지 않는다면 작은 수(b)가 큰 수가 되고, 나머지 값(c)이 작은 수가 된다.

작은 수(b)에 나머지 값(c)을 나누는 식으로 나머지가 0이 될 때까지 반복한다.

나머지가 0이 되면, 나누었던 두 수 중 작은 수가 최대공약수가 된다.

 

Javascript 예시 문법

function solution(n, m) {
  let a = m; //큰 수가 들어온다.
  let b = n; //작은 수가 들어온다.
  let r = 0; //a를 b로 나눴을 때의 나머지 값

  while (a % b > 0) {
    r = a % b;
    a = b; //큰 수에 작은 수를 할당
    b = r; //작은 수에 나머지 값 할당
  }

  // 최소공배수 : n과 m을 곱한 값에 최대 공약수를 나누면 최소공배수가 된다.
  return [b, (n * m) / b];
}