알고리즘에서 약수 개수 찾기(Feat. 제곱근까지만 검사해도 되는 이유!)

16의 약수의 개수를 찾는 코드를 작성해보자.

 

16을 1부터 16까지 반복문을 통해 나눈다.

- 만약 나누어 떨어진다면 -> 약수이다

- 나누어 떨어지지 않으면 -> 약수가 아니다

 

그런데 항상 1부터 16까지 전부를 검색해야 할까?

16의 제곱근은 4이다.

16의 약수는 1, 2, 4, 8, 16이다.

 

1, 2, 4, 8, 6

 

제곱근인 4까지만 검사하면, 나머지 약수는 4를 기준으로 대칭으로 나온다. 따라서 4보다 큰 약수를 찾을 필요 없다

 

public int countDivisors(int n) {
   int count = 0;
   int root = (int) (Math.sqrt(n));

	for(int i = 1; i <= root; i++) {
      if(n % i == 0) {   // 나누어 떨어진다면
      	if(i == Math.sqrt(number)) {
        	count++;
        } else {
			count += 2;
		}
      }
   }
   
   return count;
}