더북(TheBook)

1.6.4 최대 공약수

문제 1-17 최대 공약수(GCD, Greatest Common Divisor)를 구하세요.

해결책 유클리드(Euclid) 알고리즘을 사용해 최대 공약수를 구합니다.

GCD(n, m) == GCD(m, n mod m)

해결책 1-17

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

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.