[JavaScript] 최대공약수 구하기 (유클리드 알고리즘)

유클리드 알고리즘

두 수의 최대공약수(GCD)를 찾는 효율적인 방법

 

원리

숫자 A와 B에서 A를 B로 나누었을 때, 나머지가 R이라면 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

이 과정을 나머지가 0이 될 때까지 반복하면, 마지막으로 나눈 수가 최대공약수다.

 

ex. 48과 18의 최대공약수 찾기

48 ÷ 18 = 2 나머지 12 -> 48과 18의 최대공약수 = 18과 12의 최대공약수

18 ÷ 12 = 1 나머지 6 -> 18과 12의 최대공약수 = 12와 6의 최대공약수

12 ÷ 6 = 2 나머지 0 -> 나머지가 0이 되었으므로, 6이 최대공약수

 

구현

function findGCD(a, b) {
    // 음수인 경우 절댓값 사용, 양수인 경우 생략 가능
    a = Math.abs(a);
    b = Math.abs(b);
    
    // a와 b의 순서가 바뀌어도 최대공약수는 동일
    while(b > 0) {
        let temp = b;
        b = a % b;  // 나눈 수를 다시 나머지로 나눌 것이기 때문에 나눌 수(b)를 나머지로 업데이트
        a = temp;  // 나눈 수를 나머지로 다시 나누기 위해 나눠질 수(a)를 기존에 나눈 수(b)로 업데이트
    }
    
    return a;
}