유클리드 호제법 - 최대 공약수 구하는 알고리즘

- 큰 수를 작은 수로 나누는 과정을 반복하며, 나머지가 0이 될 때 나누는 수가 최대공약수가 되는 알고리즘

// 방법1. 반복문
const gcd = (num1, num2) => {
	let r;

	while(num2 > 0) {
    	r = num1 % num2;
        num1 = num2;
        num2 = r;
    }
	
    return num1;
}

// 방법2. 재귀 함수
const gcd = (num1, num2) => (num2 > 0 ? gcd(num2, num1%num2) : num1);

 

ex) GCD(18, 12) = 6

1. a = 18, b = 12 ➡️ r = 6
2. a = 12, b = 6 ➡️ r = 0
3. a = 6, b = 0 ➡️ X