최대공약수 구하기 - 유클리드 호제법

설명

유클리드 호제법은 최대공약수를 구하는 알고리즘 중 하나입니다.

여기서 '호제법'이라는 말은 두 수가 서로 상대방의 수를 나누어 원하는 수를 얻는 알고리즘을 나타냅니다.

2개의 자연수 a,b가 있고 a를 b로 나눴을 때(단, a>b) 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

위의 말을 귀납적으로 생각해본다면, b를 r로 나눈 나머지를 r1이라고 할 때 b와 r의 최대공약수는 r과 r1의 최대공약수가 되겠죠?

숫자를 예시로 들어보겠습니다.

예시

a: 12 b: 8 일 때

12 % 8 = 4 이므로 설명에서 말한 r은 4가 됩니다.

그렇다면 위에 설명대로 b와 r의 최대공약수 즉, 이 예시에서는 8과 4의 최대공약수가 12와 8의 최대공약수와도 같아야하죠.

숫자가 작으니 직접 해보면

12와 8의 최대공약수: 4

8과 4의 최대공약수: 4

이런식으로 반복하면 x % y = 0 이 되는데, 이 때 나누는 수가 a와b의 최대공약수가 됩니다. (위에서는 8 % 4 =0 이므로 4가 최대공약수)

코드

fun gcd(a: Int, b: Int): Int {
        var maximum = max(a, b)
        var minimum = min(a, b)

        if (minimum == 0) {
            return max(a, b)
        } else {
            return gcd(minimum, maximum % minimum)
        }
    }