[kotlin] 최대공약수와 최소공배수

 

 

 

 

나의 풀이

fun solution(n: Int, m: Int): IntArray {
    var answer = intArrayOf(0, 0)
    var a: Int = 0
    var b: Int = 0
    for (i in 1..n) {

        if (n % i == 0 && m % i == 0) {
            a = i

        }

    }

    answer[0] = a
    answer[1] = (n * m) / a


    return answer


}

 

다른 풀이 - 유클리드 호제법(Euclidean Algorithm)

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 쉽게 알아내는 방법이다.

 

 

A와 B의 최대공약수 GCD(A,B)를 알아내는 유클리드 호제법은 다음과 같다.

• A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춥니다. 
• B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈춥니다. 
• A를 A = B⋅Q + R의 형식으로 씁니다
• GCD(A,B) = GCD(B,R)이므로 유클리드 호제법을 이용하여 GCD(B,R)을 찾습니다.

최대공약수는 유클리드 호제법을 이용해 구하고
최소공배수는 n*m/최대공약수 임을 활용하여 구한다.

 

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

fun solution(n: Int, m: Int): IntArray {
    var answer = intArrayOf(0, 0)


    if(n>m){
       answer[0]=gcd(n,m) //최대공약수 구하기
    }
    else{
        answer[0]=gcd(m,n) //최대공약수 구하기
    }

// 최소공배수 구하기(최소공배수는 n*m/최대공약수 임을 활용하여 구한다.)
    answer[1] = (n * m) / answer[0]


    return answer


}