두 수의 최대 공약수, 최소 공배수 구하기 (유클리드 호제법, 자바스크립트)

코테 준비를 하다보면 두 수의 최대 공약수를 구해야 하는 경우가 보인다.

 

 

a = 100, b = 30 두수가 있을 때, 

 

a = b * x + y 에서 

기존 b 에 a 를 넣고  b 자리에는 y를 넣어 반복 하고

y가 0일 때의 b값이 최대 공약수가 된다

 

100 = 30 * 3 + 10 =>  a 에 30 b 에 나머지 10치환

30 = 10 * 3 + 0 =>  나머지 0 이므로 10이 최대공약수 가 된다.

 

코드화하면

const GCD = (a, b) => {
    if (b === 0) return a;
    return GCD(b, a % b); 
};

위 처럼 재귀함수화 하여 파라미터의 a 자리에  b를 대입하고, b 자리에는 나머지를 넣어주면 된다.

 

그럼 최소공배수를 구하는 법은?

 

 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

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

const GCD = (a, b) => {
    if (b === 0) return a;
    return GCD(b, a % b); 
};