[소인수] 구하기(Kotlin)

소인수: 어떤 수의 약수 중 소수인 수

예: 12의 소인수 = 2, 3

 

이 방식은 제곱근 범위탐색 으로 약수를 순서대로 구한 후 소수인지 판별을 해서 중복값을 허용하지 않는 Set 에 담는 방식입니다.

fun main() {
    val num = readlnOrNull()?.toInt() ?: 0
    val primeDivisors = mutableSetOf<Int>()

    for (i in 1..sqrt(num.toDouble()).toInt()) {
        if (num % i == 0) {
            if (isPrime(i)) primeDivisors.add(i)
            if (i != num / i && isPrime(num / i)) primeDivisors.add(num / i)
        }
    }

    println(primeDivisors.sorted().joinToString(", "))
}

// 소수를 확인하는 함수
fun isPrime(number: Int): Boolean {
    if (number < 2) return false
    for (i in 2..sqrt(number.toDouble()).toInt()) {
        if (number % i == 0) return false
    }
    return true
}

시간 복잡도:

약수 구하기: O( √(n) )

소수 판별: O( √(n) )

정렬함수: 자바에서 사용하는 함수를 그대로 오버라이딩 해서 사용하는거 같은데 어떤 알고리즘을 사용하는지는 잘 몰겠습니다...

일단 약수 하나를 구하고 소수를 판별하니 O( √(n) * √(n) ) = O(n) 정도가 되는거 같습니다.

 

1. 에라토스테네스의 체 를 활용한 소인수 구하기

사전에 구하고자 하는 수까지의 모든 소수를 미리 구한 후 약수들과 나누었을 때 나머지가 0 인 소수들만 리스트에 추가합니다.

fun main() {
    val num = readlnOrNull()?.toInt() ?: 0
    val primes = sieveOfEratosthenes(num)
    val primeDivisors = mutableListOf<Int>()

    for (prime in primes){
        if(prime > kotlin.math.sqrt(num.toDouble())) break
        if(num % prime == 0) primeDivisors.add(prime)
    }

    println(primeDivisors.joinToString(", "))
}

fun sieveOfEratosthenes(limit: Int): List<Int> {
    val isPrime = BooleanArray(limit + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..sqrt(limit.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..limit step i) {
                isPrime[j] = false
            }
        }
    }
    return isPrime.toList().mapIndexedNotNull { index, prime -> if (prime) index else null }
}

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

 

2. 소인수 구하기 방법2

이 방법은 제곱근 범위탐색으로 소수를 찾은 후 해당 소수가 리스트에 존재하지 안는다면 추가한 후 입력값을 해당 소수로 나누어 떨어지지 안을 때까지 나누게 됩니다. 나누어 떨어지지 안는다면 다음 소수를 찾아 동일한 과정을 반복하여 소인수를 구할 수 있습니다.

val num = readlnOrNull()?.toInt() ?: 0
var tempNum = num
val primeDivisors = mutableListOf<Int>()

for (i in 2..sqrt(tempNum.toDouble()).toInt()) {
    while (tempNum % i == 0) {
        if (!primeDivisors.contains(i)) primeDivisors.add(i)
        tempNum /= i
    }
}
if (tempNum > 1) primeDivisors.add(tempNum) // 남은 숫자가 소수일 경우 추가
println(primeDivisors.joinToString(", "))

시간복잡도: O( √ (n)​ * log(n) )

 

소인수를 구하는 알고리즘 3가지를 알아보았습니다. 이중에서 시간 복잡도가 적은것은 에라토스테네스의 체를 활용한 방법인거 같네요. 하지만 코드량은 2번째 방법이 더 적고 메모리 사용량도 적다는 장점이 있습니다.