CountFactors (Codility)

문제

정수 N이 주어진다. 이 N의 약수들의 갯수를 출력하라. 

N = 24인 경우 24의 약수는 1, 2, 3, 4, 6, 7, 12, 24 이므로 총 8개 이므로, 답은 8이다. 

 

해결 방법

1부터 N까지 나눠지는 값은 약수이다. 이 방법으로 카운트를 세서 출력하면 정답이다.

하지만 이 방법은 시간 복잡도 O(N)으로 만약 N이 int의 최대값(약 21억)으로 주어진다면 시간초과가 난다.

 

여기서 약수의 갯수를 간단하게 구하는 중요한 사실이 있다. "만약 √(N)이 정수라면 √(N)은 N의 약수이며, 나머지 약수들은 √(N)를 기준으로 앞 뒤로 짝을 이루고 있다."는 것이다.

 

예를 들어 100의 약수의 갯수를 구한다고 해보자. 

100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이다. 

√(100)은 10으로 정수이다.

즉 100의 약수는 10을 기준으로 앞 뒤로 짝을 이루고 있다는 것이다. 

(1, 100), (2, 50), (4, 25), (5, 20)으로 4개의 짝을 이루고 있으므로
2 * 4 + 1 = 9개가 된다.

√(N)을 넘어가지 않는 조건으로 (i = 1)부터 for문을 돌려 만약 N이 i로 나눠진다면 1개, 그리고 이 약수는 앞뒤로 짝을 이룰 것이므로, i^2이 N을 넘지 않는다면 1개 증가시키면 된다. 

 

주의할 점이 있는데 N의 범위는 int 범위로 [1 ~ 약 21억]까지이므로 i^2를 구하기 위해서는 더 큰 범위를 가지는 long long 자료형을 사용해야 한다.

 

구현 코드는 다음과 같다.

int solution(int N) {
    int count = 0;
	for(long long i = 1; i * i <= N ; ++i) {
    	if(N % i == 0) {
    		++count;
			if(i * i < N)
				++count;	
		}
	}	
	return count; 
}