(Python) 약수 구하기.(시간 복잡도:$O(\sqrt{n})$)

코딩테스트 문제를 풀다보면 어떤 수의 모든 약수를 구해야 할 때가 있다.

아주 간단하게 어떤 수의 약수를 구하는 알고리즘을 알아보자.추가로, 약수를 정렬된 순서로 리턴까지 해보자.

숫자 n의 약수를 구하는 알고리즘을 소개하면 다음과 같다.(시간 복잡도:$O(\sqrt{n})$)

1. 1 ~ $\sqrt{n}$의 범위안에 드는 자연수 i를 대상으로 루프를 돈다.
2. 만약 n이 i로 나누어 떨어진다면, i와 n을 i로 나눈 값은 n의 약수이다.

이를 코드로 나타내면 다음과 같다.

x = 100
divisor_set = set()
for divisor in range(1, int(x**0.5) + 1):
    if x % divisor == 0:
        divisor_set |= {divisor, x // divisor}
print(divisor_set)