[알고리즘] 약수 알고리즘

A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다.

 

모든 자연수로 나누는 방법 : O(n)

   말 그래도 1부터 N까지 모든 수로 나누어 보는 방법이다. 10이라는 숫자의 약수를 알기 위해 10번의 나눗셈 연산이 필요하다.

 

약수가 되는 성질을 이용한 방법 : O(√n)

   C가 A의 약수라면, A/C도 A의 약수가 된다. 즉 1 ~ √n 까지 구하면 된다.  

 

배수의 성질을 이용한 방법

   약수인 수보다 약수가 아닌 수가 더 많이 존재한다. 따라서 배수의 성질을 이용하면 약수만 빠르게 구할 수 있다. 알고리즘 문제 풀이에서는 주로 이 알고리즘이 사용된다. 

 

다음 그림과 함께 6을 기준으로 어떤 성질을 가지고 있는지 확인해보자.

• 6이하의 자연수 중에서 1을 약수로 갖는 수의 개수 = 6
• 6이하의 자연수 중에서 2를 약수로 갖는 수의 개수 = 3
• 6이하의 자연수 중에서 3을 약수로 갖는 수의 개수 = 2
• 6이하의 자연수 중에서 4를 약수로 갖는 수의 개수 = 1
• 6이하의 자연수 중에서 5를 약수로 갖는 수의 개수 = 1
• 6이하의 자연수 중에서 6를 약수로 갖는 수의 개수 = 1

 

 ⌊N / M⌋개의 약수를 가지는 것을 확인할 수 있다.