GCD (최대 공약수) & LCM (최소 공배수) & 유클리드 호제법

📍  GCD  :  Greatest Common Divisor  :  최대 공약수

📍  LCM  :  Least Common Multiple  :  최대 공배수  

 

 

📌  유클리드 호제법 ?

 

 

유클리드 호제법은 두 양의 정수 간의 최대 공약수를 구할 수 있는 방법이다.

단, a 가 b 보다 항상 크다는 전제가 있어야 성립한다. -> 당연한 이야기인게, a = bq + r 공식에서 이미 b는 a의 약수로 속해 있다.

a = bq + r 식은 a와 b 간의 관계를 정의한 식이다. -> a가 b 보다 크다면, b*q 값과 어떤 나머지 정수가 더해져 a를 완성할 것이다.

 

여기서 나머지 값(r) 이 0이게 되면 a와 b 사이에서는 b가 가장 큰 최대 공약수가 되는 것이다 ! 

만약 r이 0이 아니라면 ? r은 b와 어떤 정수 q의 곱으로 a 근사값을 만들어 놓고, " a와 a 근사값의 차 "  라고 정의할 수 있다.

유클리드 호제법은 0이 아닌 r과 b 사이의 최대 공약수가 a와 b의 최대공약수가 같다는 결론을 도출한 공식이다.

 

결국, 우리는 ' b ' 를 구하기 위해 애써야 한다. 

 

 

 

📌  코드로 구현

 

// 최대 공약수
function GCD(a, b){
  if(a % b === 0){
  	return b;
  }
  return gcd(b, a % b);
}

 

// 최소 공배수
function LCM(a, b){
  return a * b / GCD(a, b);
}