JavaScript - 최대공약수 구하기 (유클리드 호제법)

 

 

 

예전에 수학시간에 최대공약수 / 최소공배수 구하는 것은 누워서 껌먹기 였다. 

학원에서 가르쳐준 대로 계산하면 답이 나왔기 때문이다. 

당연히 연필들고 공책에 푸는 소인수분해의 관점에서 접근하면 머리로 이해하기는 쉬운일이지만

혹시모를 거대한 수를 다룰 가능성이 있는 IT인의 관점에서는 알고리즘을 사용하여 푸는 편이 효율적이다.

그리하여 유클리드 호제법이라는 알고리즘과 최대공약수를 구하는 법을 알고자 한다.

 

 

---

JavaScript - 최대공약수 구하기 (유클리드 호제법)

 

 

- 최대공약수

두 수의 공통된 약수 중에서 가장 큰 수

4의 약수   1, 2, 4
16의 약수 1, 2, 4, 8, 16
→ 4와 16의 최대공약수는 4이다

 

 

 

 

- 유클리드 호제법

유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.

두 수의 최대공약수를 구하는 신박한 알고리즘이다.

 

1. 두수를 A % B 이렇게 나눠서 나머지(R1) 가 생겼다.

2. 이번에는 B % R1 을 나눠버린다. 그럼 또 나머지(R2) 가 생겼다.

3. 요번에는 R1 % R2 을 나눠버린다. 그럼 또 나머지(R3) 이 생겼다.

4. 여번에는 R2 % R3 을 나눠버렸다. 근데 이번에는 나머지가 0 이다. (즉, 없다.)

그럼 두수 A 와 B 의 최대공약수는 (나머지가 멸종되기전) 마지막 나머지였던 R3 이 된다.

요런 알고리즘인데 처음 공부할때는 100%잘안가서 공책에 많이 써봤다.

 

 

 

- JavaScript 구현

구현은 생각보다 쉽다. 재귀함수를 이용해서 나머지가 0이 될때까지 다람쥐 챗바퀴돌듯 계속 호출하고,

나머지가 0 이 되는 순간 직전 나머지인 a 를 반환하고 탈출(return)한다.

  // 두수 a, b 를 넣는다.
  function greatest(a, b) {
  
    // b(나머지)가 0이면 a(직전 나머지)를 반환하고 탈출 (base case)
    if (b === 0) return a;
    
    // b를 앞으로 보내고 a % b 를 나눈 나머지(r)을 매개변수로해서 재귀함수로써 호출
    return greatest(b, a % b);
  }