[약수] 구하기(Kotlin)

약수: 어떤 수를 나누어 떨어지게 하는 수

예1) 8의 약수 -> 1, 2, 4, 8

예2) 12의 약수 -> 1, 2, 3, 4, 6, 12

 

1. Brute Force(완전탐색)

1 ~ n 까지 모든 수를 n 과 나눠보면서 판별합니다.

(방식1)

val n = 12
val divisors: MutableList<Int> = mutableListOf()
for (i in 1..n){
    if(n % i == 0){
        divisors.add(i)
    }
}
println(divisors.joinToString(", "))

 

(방식2)

val n = 12
val divisors = (1..n).filter { n % it == 0 }
println(divisors.joinToString(", "))

 

시간 복잡도: O(n)

 

2. 제곱근 범위탐색

약수는 항상 대칭으로 짝을 이루고 있습니다.

그래서 12의 약수[1, 2, 3, 4, 6, 12]  를 구한다고 했을 때 약수의 절반 인 1, 2, 3 만 구하여도

(12 / 1) = 12, (12 / 2) = 6, (12 / 3) = 4 이 됩니다. 그리고 약수의 절반은 제곱근 을 하면 구할 수 있습니다.(√(12) ≒ 3.464) 소수점은 버리시면 됩니다.

val n = 12
val divisors: MutableList<Int> = mutableListOf()
for (i in 1..sqrt(n.toDouble()).toInt()){
    if(n % i == 0){
        divisors.add(i)
        if(i != n / i){
            divisors.add(n / i)
        }
    }
}
divisors.sort()
println(divisors.joinToString(", "))

 

시간 복잡도: O(√(n))

 

3. 약수 미리계산

약수에는 규칙이 있습니다. 2 ~ n 모두 자기 자신의 수의 배수를 구하고 그 수의 약수를 보면 자기 자신의 수를 포함합니다.

2의 배수인 4, 6, 8, ... 의 약수를 구해보면

4: [1, 2, 4]

6: [1, 2, 3, 6]

8: [1, 2, 4, 8]

모두 2를 포함하고 있습니다. 3도 마찬가지 입니다. 3의 배수인 6, 9, 12 의 약수를 구해보면

6: [1, 2, 3, 6]

9: [1, 3, 9]

12: [1, 2, 3, 4, 6, 12]

로 모두 3을 포함하고 있습니다.

이 규칙을 활용해서 한번에 ~n 개의 약수를 구할 수 있습니다.

val limit = 10
val divisorsList = List(limit + 1) { mutableListOf<Int>() }
for (i in 1..limit) {
    for (j in i..limit step i) {
        divisorsList[j].add(i)
    }
}
println(divisorsList)

 

시간 복잡도: O(n log n)

 

약수를 구하는 알고리즘 3개를 살펴보았습니다.

감사합니다.