Kotlin 최대공약수/최소공배수 - 유클리드 호제법

 

 

 

 

---

1. 최대공약수 / 최소공배수

 

최대공약수(GCD, Greatest Common Divisor) 란, 두 개 혹은 그 이상의 수 간의 공통의 약수들 중 최대, 가장 큰 값을 의미한다.

 

 

 

이러한 최대공약수는 유클리드 호제법을 사용하면 간단하게 구할 수 있으며

 

구한 최대공약수를 이용하여 최소공배수 또한 구할 수 있다.

 

 

 

 

 

---

2. 코 드

환경 : Kotlin Version = 1.4.20, JVM

fun gcd(a: Int, b:Int): Int = if(b != 0) gcd(b, a % b) else a

fun main(args : Array<String>) {
    var x = 4
    var y = 10
    println("최대 공약수 : ${gcd(x, y)}")
    println("최소 공배수 : ${x * y / gcd(x, y)}")

    x = 28
    y = 16
    println("최대 공약수 : ${gcd(x, y)}")
    println("최소 공배수 : ${x * y / gcd(x, y)}")
}

 

결 과

 

- 구현한 gcd 함수를 사용하면 최대 공약수를 구할 수 있다.

 

 

 

- 최소 공배수는 두 수의 곱을 최대 공약수로 나누는 것으로 구할 수 있다.

 

 

 

 

 

---

3. 참 조

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전