Kotlin 예시 작성] 유클리드 호제법(Euclidean Algorithm)

유클리드 호제법은 최대공약수와 최소공배수를 구할 수 있는 알고리즘이다.

그니까.. 말은 이건데...

a와 b의 최대공약수는 a와 b를 나눈 나머지 r 이 존재할 때, b와 r의 최대공약수와 같다..

라는건데(???) 그래서 나머지가 0이 나오면, 그 시점의 b가 최대공약수가 된다는거다(?????)

 

예를 들어 742와 854의 최대 공약수를 구해보자.

일반적인 방식으로 구해보면...

약수집합 = [2], 371 427 ->  약수집합 = [2, 7], 53 61
최대공약수가 2*7 = 14

 

가 나오는 것을 알 수 있다.

 

유클리드 호제법은 다음과 같이 구한다.

854 = 742 * 1 + 112
742 = 112 * 6 + 70
112 = 70 * 1 + 42
70 = 42 * 1 + 28
42 = 28 * 1 + 14
28 = 14 * 2 + 0 

 

 

어라 똑같네(?)

즉 a % b = r 을 구하고 난 뒤에, a에 b 값을 넣고, b에 r값을 넣고 다시 

b % r = r' ... 이런식으로 나머지가 0이 될 때까지 반복한다

 

이를 코틀린 코드로 써보자. 설명은 주석으로 써놓았다 ㅇ.<

// 유클리드 호제법(isMuliple = true -> 최소공배수, false -> 최대공약수)
fun euclideanAlgorithm(a : Int, b: Int, isMultiple : Boolean) : Int {
    var cloneA = a
    var cloneB = b

    val result : Int
    while (true) {
        val remain = cloneA % cloneB
        if(remain == 0) {
        	// 나머지가 0이면 b를 결과로 도출가로 리턴한다.
            result = cloneB
            break
        } else {
        	// a자리에 b를, b 자리에 나머지를 넣어 해당 while문을 반복하도록 함(나머지가 0이 될때까지).
            cloneA = cloneB
            cloneB = remain
        }
    }

    return if (isMultiple) {
    	//최소공배수가 필요할 경우, 기존 값에 최대공약수를 나눈 서로소를 먼저 구한다.
        val calA = a / result
        val calB = b / result

		// 서로소와 최대공약수를 곱하면 최소공배수를 구할 수 있다.
        result * calA * calB
    } else {
        result
    }

}