[알고리즘] 최대공약수와 최소공배수 - javascript

📌 유클리드 호제법

for문을 돌려 찾을 수 있지만 유클리드 호제법을 알면 훨씬 간단하다.

큰 수(max)와 작은 수(min)가 주어졌을 때, 최대공약수를 구하는 과정을 아래와 같다.
 

1. max % min = e(1)
2. min % e(1) = e(2)
3. e(1) % e(2) = e(3)
   ...
   e(n-1) % e(n) = 0
    

• 최대공약수 : e(n)
   
• 최소공배수 : (max * min) /e(n)
   

📌 구현

function solution(n, m) {

    // 최대공약수 구하는 함수
    function u(i, j) {
        let e = i % j;
        if (e === 0) return j;
        return u(j, e);
        }

    // 최대공배수 반환
    alert(u(n,m));

    // 최소공배수 반환
    alert(n * m / u(n,m));
}

 

숫자는 큰 수, 작은 수로 나눠서 인자로 넣지 않아도 된다.

만약 n이 작은 수, m이 큰 수라면 n%m = n 이 되어 다음 재귀가 u(m,n)으로 제자리를 찾아 돌아간다.

 

간추린 코드

function solution(n, m) {
  function u(n, m) { return m % n ? u(m % n, n) : n; }
  const gcd = u(n, m);
  return [gcd, n * m / gcd];
}

 
여기서 눈여겨 볼 부분은 두 번째 줄에서 조건 설정을 m%n === 0으로 하지 않고 값이 0이 되게 하면 거짓으로 판명됨을 이용해서 m%n만으로 설정했다.

 

---

참고

제로초 블로그