[알고리즘] 유클리드 호제법

유클리드 알고리즘은 2개의 수의 최대공약수를 구하는 알고리즘의 일종이다. 

호제법이란 두 수를 나누어가며 원하는 값을 얻는 알고리즘을 의미한다.

최대공약수 (GCD, Greatest Common Divider)

최대공약수는 두 자연수가 공통으로 갖는 약수중에서 가장 큰 값을 의미한다. 

최대공약수를 구하는 코드는 다음과 같다 (자바스크립트)

 

function GCD(n, m){
    if(n % m === 0){
        return m;
    }
    return GCD(m, n % m);
}

// 반복문 버전
function GCD(n, m) {
    while (m !== 0) {
        let temp = m;
        m = n % m;
        n = temp;
    }
    return n;
}

최소공배수 (LCM, Least Common Multiple)

 

최소공배수는 두 자연수들의 배수중에서 공통된 가장 작은 수를 의미한다. 

최소공배수를 구하는 식은 다음과 같다. 

 

최소공배수 = n * m (두수의 곱) / GCD(n, m) (최대공약수)