[(코틀린)알고리즘] 약수 구하기

방법1

숫자 n이 있다면 1부터 n까지 모두 순회해서 나머지가 0인 경우를 필터링하여 찾는 방법이다.

(n까지 모두 반복문이 돌아야하기 때문에 시간복잡도가 O(n)만큼 걸린다.)

fun getDivisors(n: Int): List<Int> {
    return (1..n).filter { n % it == 0 } 
}

---

방법2

숫자 n이 있다면 1부터 √ n까지 순회해서 찾는 방법이다.

약수가 d일 때 다른 하나의 약수는 n / d가 성립하게 된다.

(√ n까지 반복문을 돌기 때문에 시간복잡도가 O(√n)만큼 단축된다.)

fun getDivisors(n: Int): List<Int> {
    val sqrt = Math.sqrt(n.toDouble()).toInt()
    val divisors = mutableListOf<Int>()
    (1..sqrt).forEach { d ->
        if (n % d == 0) {
            divisors.add(d)
            val other = n / d
            if (other != d) {
                divisors.add(other)
            }
        }
    }
    return divisors
}