[Algorithm] Kotlin 약수의 개수 구하기

0. 약간의 수학적 지식

• 어떤 수 N을 약수 m으로 나누었다면 x = N/m. 즉, x라는 또 하나의 약수가 보장된다. (제곱근이 아닌 경우)
• 예1) 35 = 5 * 7 -> 5 = 35/7. 7이라는 약수로 나누어서 5라는 약수가 보장된다.
• 예2) 4 = 2 * 2 -> 2 = 4/2. 2라는 약수로 나누어서 2라는 약수가 보장되지만, 같은 수이기 때문에 카운트하지 않는다.

1. O(N)

• for문을 사용해서 1부터 N까지의 수 중 number(타겟 숫자)와 나머지 연산을 했을 때 나머지가 0인 수를 구한다.
• O(N)이긴 하지만, number의 수가 커지면 커질 수록 비효율적인 알고리즘이 된다.

fun helper(number: Int): Int {
    var count = 0
    for (i in 1..number) {
        if (number % i == 0) {
            count++
        }
    }
    return count
}

 

2. O(√N)

• 루트를 사용하면 검사해야 하는 수가 절반으로 줄어든다.
• √N까지의 약수를 구한 후 x2를 하면 N까지의 약수의 수와 같아질 수 있다.
• 만약, √N의 값이 정수로 떨어져서 N의 제곱근이라면 +1을 해주면 된다.

fun helper(number: Int): Int {
    if (number == 1) return 1
    else if (number == 2 || number == 3) return 2

    var count = 0
    val x = Math.sqrt(number.toDouble()).toInt()

    for (i in 1..Math.sqrt(number.toDouble()).toInt()) {
        if (i * i == number) count++
        else if (number % i == 0) count += 2
    }

    return count
}