약수 개수 세기

기본적인 방법

// number : 주어진 숫자
// count : 약수의 개수

int count = 0;

for(int i=1; i<number; i++){
	if(number % i == 0){
    	count++;
    }
}

반복문을 이용해 1부터 주어진 숫자까지 1씩 더해가면서, 주어진 숫자를 나눴을 때 나누어 떨어지는 숫자를 찾는다.

 

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

---

 

약수의 특징을 이용한 개선된 방법

// number
// count

int count = 0;

for(int i=1; i*i<=number; i++){
	if(i*i=number){
    	count++;
    } else if(number%i==0){
    	count += 2;
    }
}

주어진 숫자의 제곱근까지만 확인해도, 약수의 개수를 전부 셀 수 있다!

 

반복문을 이용해 1부터 주어진 숫자의 제곱근까지 1씩 더해가면서 약수를 찾는다.

 

만약, 주어진 숫자가 반복문의 변수의 제곱인 경우, 1만 더한다.

제곱이 아닌 경우, 주어진 숫자가 반복문의 변수로 나뉘는지 확인해, 나뉘면 2를 더한다.

 

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

 

 

예를 들어 주어진 숫자가 16이면, 약수는 1, 2, 4, 8, 16 총 5개이다.

개선된 방법에서는 주어진 숫자의 제곱근인 4까지만 반복문을 수행하게 된다.

 

1은 16의 제곱근이 아니지만, 16을 나머지 없이 나눌 수 있다. 따라서 count에 2를 더한다.

2도 마찬가지이므로, count에 2를 더한다.

3은 16의 제곱근이 아니고, 16을 나누었을때 나머지가 0도 아니다. 세지 않는다.

4는 16의 제곱근이므로, count에 1을 더한다.

 

4까지 확인했으니 반복문을 종료하고 count를 보면 5가 저장되어 있다. 16의 약수의 개수와 같다!

 

 

 

 

기본적인 방법을 사용하면 속도가 느려지는 문제가 생길 수 있으니 두 번째 방법을 잘 알아둬야 할 것 같다.