[공식] 약수의 개수 구하기

약수란

어떤 수를 나누어떨어지게 하는 수를 말한다.
즉, 어떤 수를 상대로 나머지 연산을 했을 때 0이 나오게 만드는 수.

자연수 N의 약수의 개수 구하기

정석적인 방법

N보다 작은 자연수들로 N을 나눠서, 나머지가 0인 것들을 약수로 간주한다.

int numberOfDivisor(int N) {
	int cnt = 0;
	for(int i=1;i<=N;i++) {
		if(N%i==0) cnt++;
	}
    return cnt;
}

조금 더 효율적인 방법

int numberOfDivisor(int N) {
	int cnt = 0;
    for(int i=1;i*i<N;i++) {
    	if(i*i==N) cnt++;
    	else if(N%i==0) cnt+=2;
    }

자연수 N의 약수를 나열했을 때, N의 제곱근을 기준으로 위아래의 약수 개수가 동일하다는 것을 사용한 방법이다.
따라서 N의 제곱근보다 값이 작은 약수들을 구한 뒤, 그 개수에 2배를 해주면 총 약수 개수를 구할 수 있다.

ex) 10의 약수
1 2 (√10) 5 10
-> 10의 제곱근 기준 아래에 2개(1,2) 위에 2개(5,10)

이 때 유의할 경우는 N의 제곱근이 자연수일 때이다.
이 때는 N의 제곱근 또한 약수에 포함되고, 이를 처리해주어야 한다.
-> if(i*i==N) cnt++;

ex) 16의 약수
1 2 √16 8 16
-> 16의 제곱근 4가 약수 내에 포함됨