[공배수(CM), 최소공배수(LCM)] 구하기(Kotlin)

공배수: 2개 이상의 자연수 중 공통인 배수

예) 3의 배수: 3, 6, 9, 12, 15, 18, 21, 24, 27...

4의 배수: 4, 8, 12, 16, 20, 24, 28...

3과 4의 공배수: 12, 24, 36...

 

최소 공배수: 공배수중 가장 작은 수

예) 3과 4 의 최소공배수: 12

 

공배수 는 최소 공배수의 배수이기 때문에 최소 공배수 하나만 구하면 됩니다.

 

1. 최소 공배수 구하기

최소 공배수를 구하는 방법은 간단합니다. 두 수의 곱 / 최대 공약수 를 하면 구할 수 있습니다.

최대 공약수 는 이전에 구하는 방법을 포스팅 하였습니다.

https://han-studio.tistory.com/41

[공약수, 최대공약수] 구하기(Kotlin)

 

여기서는 유클리드 알고리즘을 사용해서 최대 공약수를 구하겠습니다.

fun main() {
    val num1 = 12
    val num2 = 15
    println(num1 * num2 / gcd(num1, num2))
}

fun gcd(num1: Int, num2: Int): Int{
    if(num1 % num2 == 0) return num2
    return gcd(num2, num1 % num2)
}

시간 복잡도: O(log(min(a,b)))

 

2. 공배수 구하기

fun main() {
    val num1 = 3
    val num2 = 4
    val gcd = num1 * num2 / gcd(num1, num2)
    val lcm = mutableListOf<Int>()

    for (i in gcd..gcd*10 step gcd){
        lcm.add(i)
    }
    println(lcm.joinToString(", "))
}

fun gcd(num1: Int, num2: Int): Int{
    if(num1 % num2 == 0) return num2
    return gcd(num2, num1 % num2)
}

시간 복잡도: O(log(min(a,b)) + n)