유클리드 호제법

보통 주어진 두 수의 최대공약수를 구할 땐 어렸을 적 수학시간에 배운대로 공약수로 계속 나누는 방법을 사용한다.

이 방식은 수가 크면 계산이 복잡해지고, 약수를 찾기 어렵다는 단점이 있다.

그래서 유클리드라는 수학자가 최대공약수를 구하는 알고리즘을 발견했다! 바로 유클리드 호제법이다.

유클리드 호제법으로 최대공약수를 구하는 방법은 다음과 같다.

1. 큰수를 작은수로 나눈다.
2. 나누는 수를 나머지로 계속 나눈다. -> 나머지가 0이 나오면, 나누는 수가 최대공약수다.

예시

1512, 1008의 최대공약수 구하기

1. 1512 / 1008 = 1(몫) ... 504(나머지)
2. 1008(나누는 수) / 504(나머지) = 2 ... 0
3. 나머지가 0이니, 나누는 수인 504가 최대공약수

청개구리유여사님이 알려주셨다. 감사드립니다.. 해당 영상을 보고 나니 앞으로 수학문제는 여기서 공부하면 되겠다는 확신이 생겼다.

JavaScript로 최대공약수 구하기

최대공약수는 영어로 Greatest Common Measure라고 한다. 그래서 함수 이름에 GCD를 붙였다.

const getGCD = (num1, num2) => {
   return num2 === 0 ? num1 : getGCD(num2, num1 % num2)
}

최소공배수

최대공약수가 나오면 빠질 수 없는 것이 최소공배수다. 최소공배수를 구하는 방법 중 공약수로 계속 나눠주는 방법을 생각해보자. 최소공배수는 영어로 Least Common Multiple라 한다.

A = GCD * a
B = GCD * b

그리고 나서 A를 구하는 식과 B를 구하는 식을 서로 곱해보자.

A * B = GCD * a * GCD * b

순서를 조금 바꿔보자.

A * B = GCD * a * b * GCD

그림에서 볼 수 있듯이 LCM은 GCD * a * b이므로 다음과 같이 바꿀 수 있다.

A * B = LCM * GCD

LCM을 구하기 위해서는 각 항을 GCD로 나눠주면 되겠다!```

LCM = A * B / GCD

JavaScript로 최소공배수 구하기

지금까지 살펴본 결과 최대공약수와 최소공배수의 관계를 알 수 있었다.
두 자연수의 곱 = 최대공약수 * 최소공배수라는 것이다.
앞서 JavaScript로 최대공약수를 구하는 함수를 작성했으니 이를 활용하면 된다.

const getLCM = (a, b) => {
  return a * b / getGCD(a, b)
}

관련 알고리즘 문제

• BAEKJOON-1934
• BAEKJOON-2609
• BAEKJOON-9613
• BAEKJOON-17087

참고

• 수학방 - 최대공약수와 최소공배수의 관계
• 청개구리유여사 - 최대공약수 구하기 : 유클리드 호제법