약수를 빠르게 구하는 알고리즘

1. 설명

 

어떤 자연수 n에 대하여 n = a*b가 되는 두 자연수 a,b를 n의 약수라고 한다.

 

이러한 a,b는 반드시 존재한다. 최소 (1,n)이 존재한다는 것.

 

n의 약수를 프로그래밍으로 어떻게 구할까?

 

가장 쉽게 생각하는 방법은 n을 1부터 n까지 각각 나눠보면서 나누어 떨어지는 수를 찾는 것이다.

 

그런데 n이 너무 크면, 10억만 되어도 너무 오래걸린다는게 문제

 

-----------------------------------------------------------------------------------------------------------------------

 

그런데 n = a*b에서 a,b의 관계를 생각해보면 a > b, a < b, a = b 3가지 경우가 가능하다.

 

근데 사실 a > b와 a < b는 그냥 서로 자리를 바꾸면 되는 것으로 똑같은 경우다.

 

그리고 a를 어떻게든 찾는다면, b는 n을 a로 나눈 몫이므로 b를 찾은거나 마찬가지다.

 

일반적으로 a >= b라고 가정할 수 있고 b의 최댓값은 a가 된다.

 

그럴때 n = a * a이므로, 우리는 1부터 n의 제곱근까지 검사해서 n에 대해 나누어 떨어지는 수를 찾는다면

 

그에 대응하는 b를 모두 찾을 수 있다는 점이다.

 

2. 예시 코드

 

div_list = []

for div in range(1,int(n**(1/2))+1):
    
    if n % div == 0:

        div_list.append(div)

        if div**2 != n:

            div_list.append(n//div)

 

약수인지 검사하는 알고리즘으로 제곱근까지 검사하는건 해봤는데.. 약수를 전부 구하는건 생각을 안해봤으니 ㅋㅋㅋ

 

사실 똑같은건데 ㅋㅋㅋㅋ 대응하는 b를 찾기 위해 몫을 넣는다는 것을 생각을 못해봤으니.. 이게 응용이 안되네

 

3. 예시 문제

 

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

 

자연수 N,K가 입력으로 주어질 때, N의 약수중에서 K번째로 작은 약수를 출력하는 문제

 

만약 N의 약수의 개수가 K보다 작아서 K번째로 작은 약수가 존재하지 않으면 0을 출력

 

약수를 빠르게 구하는 위 알고리즘을 사용해서 약수 리스트를 구하고, 정렬한 뒤에 K-1번째 원소에 접근하여 출력

 

만약 에러나면 0을 출력

 

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

div_list = []

for div in range(1,int(N**(1/2))+1):
        
    if N % div == 0:

        div_list.append(div)

        if div**2 != N:

            div_list.append(N//div)

div_list.sort()

try:
    
    print(div_list[K-1])

except:
    
    print(0)

 

 

참조

 

https://minnit-develop.tistory.com/16

[Algorithm/Python] 파이썬 약수 구하기 (시간복잡도 줄여보기)