효율적으로 약수 구하기

어떠한 양의 정수 N의 약수를 구할 때 간단하게 생각해보면 다음과 같이 1부터 N까지 나누어보면 쉽게 구할 수 있다는 것은 누구나 생각할 수 있다.

def get_divisor(num):
	res = []
    for i in range(1, num + 1):  
        if num % i == 0:
           res.append(i) 
    return res

하지만 이는 O(N)의 시간 복잡도를 가지므로 N이 매우 커진다면 시간 초과로 문제를 풀 수 없을 것이다.

 

잘 생각해보면 우리는 약수를 구할 때 1부터 N까지 모두 확인해볼 필요가 없다.

우리는 1부터 N의 제곱근까지만 확인해보면 된다.

어떻게 구할거냐면

1. 1부터 N의 제곱근까지의 수들 중 N과 나누어 떨어지는 수들을 구한다.
2. 그 수들을 N에 대해 다시 나누어서 나머지가 0이 되는, 즉, 나누어 떨어지는 수들을 구하면 N의 모든 약수를 구할 수 있다.

파이썬 코드로 구하면 다음과 같다.

def get_divisor(num):
    res = []
    # 일단 num의 제곱근까지만 약수 구하기
    for i in range(1, int(math.sqrt(num)) + 1):  
        if num % i == 0:
           res.append(i) 
    # 제곱근까지만 구한 약수들 가지고 num을 나눠서 나머지 약수 구하기
    l = len(res)
    for i in range(l):
        res.append(num // res[i])
    return sorted(set(res))

중복을 제거하고 오름차순으로 정렬하기 위해 set 자료구조와 sorted 함수를 사용하여서 리턴값은 집합으로 나올 것이다. 

 

[참고]

[알고리즘] 효율적으로 약수를 찾는 알고리즘