약수의 개수 알고리즘

public int countDivisor(int num) {
    double sqrt = Math.sqrt(num);
    int count = 1;

    for (int i = 2; i <= sqrt; i++) {
        if (num % i == 0) count++;
    }

    return sqrt == Math.floor(sqrt) ? count * 2 - 1 : count * 2;
}

 

1부터 n까지의 숫자를 i로 나누어 떨어지는 수를 count 에 더하면 시간 복잡도가 O(n)이 나오게 된다.

하지만, 약수의 개수를 구할 때에는 해당 숫자의 제곱근까지만을 구한 후 2배를 해주면 된다.

 

20을 예로 들자면, 20의 제곱근은 4.xxx이다.

20을 1부터 4까지 각각 나누어서 나누어 떨어지는 수는 아래와 같다.

 

20 % 1 = 0

20 % 2 = 0

20 % 3 = 2

20 % 4 = 0

 

따라서 1, 2, 4는 20의 약수가 된다.

이번엔 1, 2, 4로 20을 나누게 되면 아래와 같다.

 

20 / 1 = 20

20 / 2 = 10

20 / 4 = 5

 

따라서 5, 10, 20도 20의 약수가 된다.

 

위와 같은 방식으로 약수를 구하게 되면 시간 복잡도도 O(sqrt(n))으로 줄어들게 된다.