모든 수를 검사

  일반적으로 n의 약수의 개수를 구할 때 n을 1부터 n까지 정수로 나눠 약수인지 판별하는 로직을 생각해낸다. 코드는 아래와 같다.

public class ex {
    public static void main(String[] args) {
        int n = 32;
        int count = 0;
        for(int i = 1; i <= n; i++) {
            if(n % i == 0)
                count ++;
        }
        System.out.println("count = " + count);
    }
}

위 로직은 시간복잡도가 O(n)으로 괜찮긴 하지만 아래 방식들이 더 효율적이다.

2/n 까지 검사

  n의 약수를 구할 때 n 자기 자신을 제외하고는 n/2보다 클 수 없다. 따라서 절반까지만 검사하면 된다.

public class ex {
    public static void main(String[] args) {
        int n = 32;
        int count = 0;
        for(int i = 1; i <= n/2; i++) {
            if(n % i == 0)
                count ++;
        }
        // n자기 자신 카운트
        count ++;
        System.out.println("count = " + count);   
    }
}

첫 번째 방식에 비해 절반가량 연산을 줄일 수 있다. 하지만 n/2보다 검사 대상을 더 줄일 수 있다.

sqrt(n)까지 검사

  n의 약수 중 하나가 a라고 하면, 다른 약수는 n/a가 되므로 하나의 약수를 알면 다른 하나를 알 수 있다. 그렇다면 1부터 어디까지 검사를 해야 n의 약수의 절반을 구할 수 있을까?

정답은 n의 제곱근까지만 검사하면 n의 약수의 개수를 구할 수 있다.

public class ex {
    public static void main(String[] args) {
        int n = 32;
        int count = 0;
        for(int i = 1; i <= Math.sqrt(n); i++) {
            if(i*i == n)
                count++;
            else if(n % i == 0)
                count += 2;
        }
        System.out.println("count = " + count);
    }
}

시간복잡도는 O(sqrt(n))이다.

증명 : 참고

기타

• 참고로 n이 제곱수면 약수의 개수는 홀수, 그 외는 짝수

  ex)
  16 -> 5개
  18 -> 6개

• 소수 판별 알고리즘에서도 마찬가지로 sqrt(n)만큼만 검사하면 된다.