최대 공약수(Greatest Common Divisor, 이하 GCD)는 두 개 이상의 정수의 공통 약수 중에 가장 큰 정수를 의미합니다. 이번 글에서는 코틀린으로 두 정수의 GCD를 찾는 알고리즘을 작성하는 방법에 대해 알아보겠습니다.

유클리드 호제법 알고리즘

가장 널리 사용되는 GCD 알고리즘은 유클리드 호제법(Euclidean Algorithm)입니다. 두 정수 a와 b에 대해 a > b 일 때, a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지 r의 최대공약수와 같습니다. 이를 재귀적으로 반복하면 됩니다. 이 알고리즘을 사용하여 코틀린 코드를 작성해보겠습니다.

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}

위의 코드는 재귀 함수를 사용하여 두 정수의 GCD를 계산합니다. 첫 번째 인자인 a가 두 번째 인자인 b보다 크거나 같도록 보장하고, b가 0이 되면 a가 GCD가 됩니다.

이제 이 함수를 사용하여 GCD를 계산할 수 있습니다.

fun main() {
    val a = 24
    val b = 36
    val result = gcd(a, b)
    println("최대 공약수는 $result 입니다.")
}

결론

이상으로 코틀린으로 최대 공약수를 계산하는 유클리드 호제법 알고리즘에 대해 알아보았습니다. 이를 통해 두 정수의 최대 공약수를 효율적으로 계산할 수 있습니다.