[Python] 약수 구하기 [최적화]

약수

어떤 자연수를 나누어 떨어지게 하는 수로, 약수는 항상 1과 자기 자신을 포함한다.

약수를 구하는 방법

1. 단순한 방법

• 1부터 자기 자신까지 1씩 증가하면서 나누어 떨어지는 경우, 즉 나머지가 0인 경우 리스트에 추가해준다.

• 시간 복잡도 : O(n)

  def divisor(number):
      result = []
      for i in range(1, int(number**(1/2))+1):
          if number%i==0:
              result.append(i)
      return result

2. 효율적인 방법

• 어떤 수 N의 약수는 항상 $N=A*B$로 나타낼 수 있다는 점에서 착안하여, A를 구할 경우 B까지 리스트에 추가해주는 방식으로 효율화를 이룰 수 있다.

  ex) 16의 약수
  
  1 x 16 ⇒ result = [1, 16]
  2 x 8 ⇒ result = [1, 16, 2, 8]
  4 x 4 ⇒ result = [1, 16, 2, 8, 4]
  
  4까지만 탐색해도 16의 약수를 모두 구할 수 있다

• 위와 같은 방식으로 구현할 경우, 기존의 방식의 시간 복잡도 $O(n)$을 $O(n^{1/2})$까지 줄여준다

  def divisor(number): # number : 16
      result = []
      for i in range(1, int(number**(1/2))+1):
          if number%i==0:
              result.append(i)
              if i < number//i:
                  result.append(number//i)
          		# [1, 16, 2, 8, 4]
  		result.sort() 
          		# [1, 2, 4, 8, 16]
      return result 

관련 문제

• 백준 2981번 검문