[Kotlin] 백준 2501 - 약수 구하기

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

풀이

1. 나머지가 0으로 나누어 떨어지면 약수이다.

2. N이 10,000이하이다 -> 무식한 방법인 1부터 N까지 모두 확인해도 1만분의 1초(1억에 1초로 가정)

3. 시간복잡도 O(N)이지만 N이 1억 이하로 작기에 방법을 채택한다.

제출 코드

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val N = nextInt()	// 입력값 받기
    val K = nextInt()	// 입력값 받기
    var C = 0
    
    // 1부터 N까지 루프
    for(i in 1..N){
        // 약수
		if(N%i == 0){
            C++
            // K번째 약수
            if(C == K){
                // 출력
                println(i)
            }
        }
    }
    
    // 약수 확인 종료
    if(C < K) println(0)
}