[🥉3 / 백준 2501 / 파이썬] 약수 구하기

 

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 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

 

예제 입력 1 6 3	예제 출력 1 3
예제 입력 2 25 4	예제 출력 2 0
예제 입력 3 2735 1	예제 출력 3 1

 

풀이

 

1부터 n까지 수를 올려가며 n을 나눈다.

만약 나누어 떨어질 경우 k를 하나씩 감소시킨다.

k가 0이 된다면, 현재 수가 k번째 작은 약수이므로 현재 수를 출력하고 break 한다.

k가 0이 되기전에 반복문이 끝난다면 약수의 개수가 k개 보다 적다는 의미이므로 0을 출력한다.

 

n,k = map(int,input().split())
for i in range(1,n+1):
    if n % i == 0:
        k -= 1
    if k == 0:
        print(i)
        break
else:
    print(0)