최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

두 수의 최대공약수와 최소공배수를 반환한다.

fun solution(n: Int, m: Int): IntArray {
    var gcd = 0
    val lst = MutableList(0) { 0 }
    var notfound = true
    for (i in 1..sqrt(n.toFloat()).toInt()) {
        if (n % i == 0) {
            gcd = n / i
            if (m % gcd == 0) { notfound = false; break }
            lst.add(i)
        }
    }
    if (notfound) gcd = lst.last { m % it == 0 }
    return intArrayOf(gcd, n * m / gcd) }

최대공약수부터 구한다.
두 수가 나누어 떨어지는 가장 큰 수를 구하면 되는데, 성능을 위해서 n에 대해 제곱근까지만 탐색하고, n을 나누어 떨어지는 수의 짝이 되는 약수가 m을 나누어 떨어지는지 확인한다. 그렇다면 최대공약수를 구한 것이고, 아니라면 작은 약수를 배열에 저장해뒀다가 나중에 거꾸로 순회시킨다.

최대공약수를 구했다면 최소공배수는 n * m / gcd 이다.