[브루트포스/수학] 백준 2501 약수 구하기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2501번: 약수 구하기

 

 

 

2. 문제 풀이

 N의 K번째 약수를 구하는 문제입니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 1부터 N까지 1씩 늘려가며, 약수가 맞는지 확인합니다.

 

 

 

3. 코드

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

cnt = 0
for divide in range(1,N+1):
    # 약수일 경우, cnt + 1
    if N % divide == 0:
        cnt += 1

    # k번째 약수일 경우, 출력
    if cnt == K:
        print(divide)
        break
# k번째 약수 없음
else:
    print(0)

 나머지가 0이면, N을 나눈 수는 N의 약수입니다. 1부터 N까지 1씩 늘려가며, 나눈 다음 나머지가 0인 약수를 찾습니다. count(cnt)가 k번째인 약수를 찾으면 출력합니다.

 만약 없다면 0을 출력합니다. 파이썬에서는 for-else구문을 사용해서 쉽게 구현할 수 있습니다.