[백준 2501] 약수 구하기

[ 백준 2501 : 약수 구하기 ]


한 자연수의 약수를 구한 후 약수 중 k번째로 작은 수를 구하면된다.
일단 약수 구하는 식은 뻔하고 약수나 소수 구하는 소스는 이전에도 많이 게시했었는데 그래도 다시 한번 로직을 올려본다.

-약수 구하는 로직-
약수를 구할 자연수 N에 대해서 총 시간 복잡도는 SQRT(N) [N 제곱근] 이 걸린다.
자명한 시간복잡도인데 16라는 수를 생각해보자.
16의 약수 = 1 2 4 8 16 이렇게 나오는데
16은 1로 나누어떨어지고 1로 나눌때의 몫이다. 이렇게 1과 16이 구해진다.
16은 2로 나누어떨어지고 2로 나눌때의 몫은 8이다. 이렇게 2과 8이 구해진다.
16은 4로 나누어떨어지고 4로 나눌때의 몫은 4이다. 이렇게 4가 구해진다.
이제 4보다 큰 수는 없다. 4보다 큰수는 이미 4보다 작은수로 나눴을때의 몫으로 구해졌기때문이다.
-끝-

그럼 이런 방식으로 약수를 모두 구한다. N의 범위가 1만이므로 O(100)안에 구해지니까 시간은 통과
그리고 소팅을 한다. 그럼 최악에 100*log100

그 후 k-1번째 인덱스의 수를 출력하면된다.