약수 구하기

자연수 N (N > 0)이 주어졌을 때 N의 약수 구하기

 

👉 단순한 방법

def find_divisor(n):
    divisors = []

    for i in range(1, n + 1):
        if n % i == 0:
            divisors.append(i)

    return divisors


num = 100
print(find_divisor(num)) # [1, 2, 4, 5, 10, 20, 25, 50, 100]

• 반복문을 1부터 n까지 돌려준다.
• 만약 n을 i로 나누었을 때 나누어 떨어지면 약수이므로 divisor_list 배열에 저장해준다.
• 시간복잡도: O(N)

 

 

👉 좀 더 효율적인 방법

def find_divisor(n):
    divisors = []

    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    print(divisors)  # [1, 100, 2, 50, 4, 25, 5, 20, 10]
    divisors.sort()

    return divisors


num = 100
print(find_divisor(num))  # [1, 2, 4, 5, 10, 20, 25, 50, 100]

• 1부터 n까지 반복문을 돌지 않고 n의 제곱근까지만 도는 방법이다.
• n을 i로 나누었을 때 나누어 떨어지면 divisor_list에 추가한다.
• 근데 이렇게 하면 제곱근까지 반복하므로 약수가 절반밖에 구해지지 않는다.
• 그래서 약수로 divisor_list에 들어간 i의 짝인 n // i 를 divisor_list에 추가해주는데 i와 n // i가 같다면 중복되는 값이 존재하므로 if문으로 걸러준다.
• 시간복잡도: O(N^0.5)

 

약수를 구하는 문제는 아니었지만 약수가 짝수개인지 홀수개인지 구하는 알고리즘 문제를 풀던 중에 문제 접근을 하다가 궁금해서 찾아보고 생각해본 내용을 정리했다.

 

문제는 프로그래머스 '약수의 개수와 덧셈'

 

끝!