GCD 란?

최대공약수는 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미한다. 주어진 두 자연수의 최대공약수를 구하려면, 우선 두 수의 약수중에서 공통된 것을 찾아 그 값 중에서 최대인 것을 찾으면 된다.

In mathematics, the greates common divisor(gcd) of two or more integers, which are not all zero, tis the largest positive integer that divides each of the integers.

GCD Algorithm

• 두 자연수 중에서 더 작은 값을 기준으로 그 값이 공통된 약수인지 검토한다.
• 공통된 약수일 경우 이 값을 반환해주고, 공통된 약수가 아닐 경우 자연수 중 작은 값을 1만큼 감소하여 공통된 약수인지 검토한다.

function gcd(str) {
    // str은 "22 24"와 같이 숫자 사이에 띄어쓰기가 한 칸씩 있는 것으로 가정한다.
    var array = str.split(" ").map(Number).sort();
    
    for (var i = array[0] - 1; i > 0; i--) {
        if (array[0] % i === 0 && array[1] % i === 0) {
            return i;
        }
    }
}

Euclid’s Algorithm

In mathematics, the Euclid’s algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them withouth leaving a remainder. (wikipedia)

수학자로 유클리드는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다.

• a와 b의 최대공약수는 ‘b’와 ‘a를 b로 나눈 나머지’의 최대공약수와 같다. 즉 gcd(a, b) = gcd(b, a % b) 이다.
• 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n 이다.

결국, 주어진 두 수를 나눈 나머지가 0이 될 때까지 gcd함수를 재귀적으로 호출하면서 나머지가 0이 될 때 값을 반환해준다.

function gcd(str) {
    var array = str.split(" ").map(Number);
    var firstNum = array[0];
    var secondNum = array[1];
    
    if (secondNum === 0) {
        return firstNum;
    }
    
    str = secondNum + " " + (firstNum % secondNum)
    return gcd(str);
}