최대공약수와 최소공배수(GCD, LCM)

프로그래머스의 최대공약수와 최소공배수 문제를 해결 후 다른 개발자 분들의 풀이를 보았다가 두 눈을 의심하였다.

문제를 보기 전에 최대공약수와 최소공배수(GCD, LCM)에 대해 간략하게 정리해보겠다.

두 정수 a, b의 공약수는 a의 약수이자 b의 약수인 정수이고, 공배수는 a와 b 모두의 배수가 되는 정수이다.
이 때 최대공약수(GCD, Great Common Divisor)는 가장 큰 공약수를 의미하며,
최소공배수(LCM, Least Common Multiple)은 가장 작은 공배수를 의미한다.

유클리드 호제법(Euclidean algorithm) : a를 b로 나눈 나머지를 r이라고 했을 때,
GCD(a, b) = GCD(b, r)이 성립한다.

function gcdlcm(a, b) {
  var r;
  for(var ab= a*b;r = a % b;a = b, b = r){}
  return [b, ab/b];
}

for문이 어떻게 돌아가는 건지 궁금하여 머릿속으로 천천히 되새김해보았다.

선언문(var ab = a*b)
a에 b를 곱한 값을 선언한 변수 ab에 할당

조건문(r = a % b)
이 부분이 해당 코드의 꽃이라 볼 수 있다.
조건문 안에 있는 값이 true이면 반복문이 계속 진행되는데, r = a % b에 대한 출력값으로 a % b가 나오므로 이 값이 0이 아니면 true로 인식하게 되고, a가 b로 나누어 떨어지는 경우(a % b === 0) 반복문이 종료되는 것이다.

증감문(a = b, b = r)
유클리드 호제법에서 GCD(a, b) === GCD(b, a % b)에 대한 부분이라고 할 수 있다.(조건문에서 r = a % b)

내용 출처 : https://torbjorn.tistory.com/244
썸네일 출처 : https://velog.io/@jelkov/Algorithm-with-Math-GCD-LCM