최대공약수와 최소공배수를 쉽게 구하는 유클리드 호제법

'호'는 한자로 서로 호, '제'는 덜 제 라고 한다.

서로 두 수를 나눈다라는 뜻이라고 한다.

 

- 최대공약수 -

 

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는

b와 r의 최대공약수와 같다.

 

이 성질을 이용해 반복해서 나머지가 0이 나올 때까지 나누면 그 수가 최대공약수라고 한다.

 

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

 

- 최소공배수 -

 

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

 

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

위에서 구한 최대공약수로 최소공배수는 쉽게 구할 수 있다고 한다.

호제법을 전에 공부했는데 오랜만에 보니 기억이 안나서 다시 정리를 했다.

 

 

출처 : https://imkh.dev/algorithm-gcd-lcm/

최소공배수와 최대공약수 알고리즘 (유클리드 호제법)