분류

  • 약수 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_divisor(n):
    divisor = []

    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            j = n // i
            divisor.append(i)
            if i != j:
                divisor.append(j)

    divisor.sort()

    return divisor

약수의 성질을 이용하기 때문에 $O(n^{0.5})$의 복잡도만에 약수를 모두 구할 수 있다.

순서대로 표시할 필요가 없다면 sort()는 하지 않아도 된다.