[백준 11653번] [Kotlin] 소인수분해

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

난이도 : 브론즈 1
태그 : 수학, 정수론, 소수 판정

 

 

설명

N에 대해 소인수분해를 하는 문제입니다.

 

소인수분해 과정은 꽤 간단합니다.

60을 소인수분해 한다 했을때,

60 / 2 = 30 이며,

30 / 2 = 15 입니다.

2로는 더 이상 나눠지지 않으니 3으로 나눠봅시다.

15 / 3 = 5 이며,

더 이상 3으로 나누어지지 않고, 4로도 나누어지지 않습니다.

5 / 5 = 1 입니다.

이와 같이 60을 소인수분해 하면 2 * 2 * 3 * 5 = 60을 구할 수 있습니다.

 

 

소스코드

fun main() {
    var n = readLine()!!.toInt()
    val sb = StringBuilder()

    var cnt = 2
    while (n > 1) {
        // 나누어 떨어질 때
        if (n % cnt == 0) {
            sb.append(cnt).append("\n")
            n /= cnt
        } else {
            // 나누어 떨어지지 않을 때
            cnt++
        }
    }

    print(sb)
}

위의 개념을 코드로 표현한 것입니다.

cnt는 2부터 시작하여 더 이상 나누어 떨어지지 않으면 +1 씩 증가하며,

n이 1보다 큰 동안 반복합니다.

즉 n = 1이 될때 while문을 탈출합니다.

 

이를 StringBuilder에 쌓아 뒀다가 출력합니다.

 

 

후기

소인수분해는 이 문제처럼 단독 문제로 출제될 때도 많지만,

문제를 풀기 위해 소인수분해를 해야하는 문제도 꽤나 많습니다.

알아두면 나름 유용하게 쓰이더군요.