최대공약수, 최소공배수

최대 공약수

방법 1
반복문으로 1 ~ 최대 공약수를 구하려는 숫자들 중 가장 작은 수 돌려서 하면 되기는 하는데...
시간 복잡도: O(N) 으로 너무 오래걸린다.

방법 2
유클리드 호제법을 이용한 방법
시간 복잡도: O(Log N)
A를 B로 나눈 나머지를 R이라 하자. GCD(A,B) = GCD(B,R) 이고 R = 0일때의 B의 값이 최대 공약수이다.

ex) A = 24, B = 16
GCD(24, 16) = GCD(16, 8) = GCD(8, 0)
최대 공약수: 8

만약 여러 수의 최대 공약수를 구하려면
A와 B의 최대공약수를 A''
A' 과 C의 최대공약수를 A''
A'' 과 D의 최대공약수를 A'''
최대공약수는 A'''가 된다.

최소 공배수

구하고자하는 숫자들에서 최대공약수 만큼 나눈 후 그 값들과 최대 공약수를 곱한 값

코드로 구현

const getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

const getLCM = (num1, num2) => {
  const gcd = getGCD(num1, num2);
  return (num1 * num2) / gcd;
};

참고: https://url.kr/92nodz