December 31, 2022

2501번: 약수 구하기

문제 요약

• 두 수 N과 K가 주어졌을 때, N의 약수 중 K번째로 작은 수를 찾는 문제이다.
• K번째로 작은 수가 존재하지 않을 경우 0을 출력한다.
• 1 ≤ N ≤ 10,000, 1 ≤ K ≤ N
• 시간 제한 : 1초

풀이

N, K = map(int, input().split())

def solution():
    cnt = 0

    for i in range(N):
        if (N % (i + 1) == 0):
            cnt += 1
            if (cnt == K):
                print(i + 1)
                return

    print(0)

solution()

• N을 1부터 N까지의 수로 나눠 K번째로 작은 수를 찾았다.

시간 복잡도

• O(N)
• N의 크기가 커질수록 더 많은 시간이 소요된다.