[JAVA] 자바로 숫자의 약수 갯수 구하기

📌  자바로 숫자의 약수 갯수 구하기

자바로 특정 숫자의 약수 갯수 구하는 방법 

숫자 n의 약수 갯수를 구한다고 할 때 1부터 시작해서 1씩 더해가면서 n을 나눈 나머지가 0이 되면 약수이니까 1씩 더해 주면 된다.

이게 가장 정석적이고 보편적인 풀이이다.

public int countDivisor(int n) {
	int answer = 0;
    
    for (int i = 0; i <=n; i++) {
    	if (n % i == 0) {
        	answer++;
        }
    }
}

그런데 n이 커지면 커질 수록 약수의 갯수를 구하는 데 걸리는 시간도 길어진다.

(예를 들어 n이 2944231이라면 2944231번 약수가 맞는지 계산해야 한다.)

시간 복잡도를 잡아먹는다. 

특히나 효율성도 확인하는 코테에서는 1씩 더해가면서 순회할 때 시간초과가 나기도 한다.

이런 경우를 위해서 약수의 갯수를 구하는 데 사용되는 시간을 줄이는 법이 있다.

 

📌  자바로 숫자의 약수 갯수 더 빨리 효율적으로 구하기 

1부터 n의 제곱근까지만 확인해서 약수의 갯수를 알아내는 방법이다.

예를 들어 n의 약수 a를 구했다고 할 때 a에는 항상 곱했을 때 n이 되는 짝꿍인 b가 있다. 

 

그렇기 때문에 n의 제곱근까지만 순회해서 약수의 갯수를 구하면 해당 약수의 갯수는 그 2배가 된다는 것을 알 수 있다. 

이 때 주의해야 할 점은 제곱근인 경우이다. 

예를 들어 16의 약수의 갯수를 구할 때 4는 16의 제곱근이므로 약수 1개만 더해주어야 한다.

 

해당 부분만 분기처리하면 훨씬 빠르게 약수의 갯수를 구할 수 있다.

public int countDivisor(int n) {
	int answer = 0;
    
    for (int i = 0; i <= n * n; i++) {
    	if (n % i == 0) {
        	
            if (i * i == n) {
            	answer++;
            } else {
            	answer += 2;
            }
        }
    }
}