단순하게 약수의 개수를 구하는 방법은 1 ~ N 까지 순차적으로 나머지 연산을 하여 0으로 나누어 떨어지는지 체크하는 방법이다. 그렇게 구하게 된다면 N까지 구해야하므로 시간복잡도는 O(n)이 되게 된다.

// 위의 방식으로 구현한 코드
for(int i = 0; i<= n; ++i)
{
   if(i % n == 0)
	 {
			// 약수이다.
	 }

}

하지만 특정 문제를 해야해야 하기 위해서는 해당 방법보다 더좋은 효율의 방법을 찾아야 할때도 있다.

위 방법 대신 약수의 개수를 구하기 위한 방법의 알고리즘의 시간복잡도는 O(logN)이다.

제곱근 만큼만 구하기

자연수 N이 존재 할 때, 약수는 절대 N의 제곱근 초과 ~ N 미만의 수가 될 수 없다. ( 9가 존재할때 9의 약수는 4를 초과할수 없다. N = 9 , N = a * b 이라고 했을때 9의 제곱근인 3을 기준으로 1 * 9 , 3 * 3 , 9 * 1 이기 때문이다)

int getDivisorsCount(int number) // 1 ~ number까지의 약수의 개수를 새는 코드
{
    int cnt = 0;
       for (int i = 1; i * i <= number; i++) {
           if (number % i == 0) {
               
               if(number / i == i)
               {
                   cnt++;
               }
               else // number 자신도 약수에 포함시켜야하기 때문에 +1 더해줘야함.
               {
                   cnt += 2;
               }
           }
       }
     
       return cnt;
}