약수 찾기 알고리즘

개요

흔히 기본적인 알고리즘이라고 불리는 약수 찾이 알고리즘을 파이썬을 이용해 살펴보자.

나는 이 기본적인 알고리즘조차 구현해내지 못했다...^^

 

약수 찾기 알고리즘

바로 본론으로 들어가겠다.

 

보통 약수 찾기는 이렇게 구현할 수 있다.

나는 생각 못했지만.

a = 9
b = 10

for num in range(a, b + 1):
    for i in range(1, num + 1):
        if num % i == 0:
            print(i)

9와 10의 약수를 구해주는 코드이다.

난 왜 이것도 생각 못했지.

예전에 쓴 적은 있는 것 같은데...

 

더 효율적인 방식으로 들어가보자!

a = 9
b = 10

for num in range(a, b + 1):
    for i in range(1, int(num**(1/2))+1):
        if num % i == 0:				(1)
            print(i)
            if i ** 2 != num:				(2)
                print(num // i)

 

결과만 말하면, 우리가 약수를 찾으려는 값의 제곱근까지만 탐색을 해주면 그 값의 모든 약수를 구할 수가 있다.

사실 위의 (1)까지는 이해가 될 것이라고 생각한다.

하지만 (2)는 왜 존재할까?

약수를 찾으려는 값을 약수로 나누면 또 약수가 나온다는 걸까? 그 말이 맞다.

 

우리가 약수를 찾으려는 숫자가 10이라고 가정하자.

그리고 저 코드를 한 줄 한 줄 거쳐보자.

 

현재 for i in range(1, int(10 ** (1/2)) + 1)에 도착했다.

1부터 int(10 ** (1/2)) + 1의 결과 4까지 i가 증가한다.

 

10 % 1 == 0

10 % 2 == 0

10 % 3 != 0

10 % 4 != 0

(1)번을 거쳐 1과 2가 출력된다.

 

이제 (2)번의 차례다.

1 ** 2 != 10이다.

2 ** 2 != 10이다.

 

그럼,

10 // 1 == 10

10 // 2 == 5

(2)번을 거쳐 10과 5가 출력된다.

 

그럼 총 출력은 무엇이냐?

1

2

10

5

 

그리고 10의 약수는 1,2,5,10이다.

 

두 코드의 차이는 시간복잡도에서 발생한다.

맨 위의 코드는 O(n)의 시간복잡도를 가진다. (약수를 찾을 정수를 읽는 첫 번째 for문은 제외했다.)

하지만, 우리가 본 제곱근을 이용한 약수 찾기 코드는 O(n**(1/2))의 시간복잡도를 가진다. (마찬가지로 약수를 찾을 정수를 읽는 for문은 제외했다.)

 

오늘 알아본 약수 찾기 알고리즘을 통해, 약수를 찾을 때 걸릴 코드의 시간복잡도가 2배나 줄어들었다.