유클리드 호제법 (최대공약수)

문제

두 자연수 a, b의 최대공약수(GCD)를 구해서 출력한다.

유클리드 호제법을 재귀 함수로 구현해 보자.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

원리: gcd(a, b) = gcd(b, a mod b)이고, b가 0이 되면 a가 최대공약수이다.