[Algorithm-PS] 약수의 개수

 

알고리즘 문제를 풀 때

종종 약수의 개수를 물어보는 문제들이 출제된다.

 

입력 수를 number 라고 할 때,

가장 쉬운 방법으로는 1부터 number로 number를 나눠서

나누어 떨어지면 count를 1 증가시키면 된다.

해당 방법의 시간 복잡도는 O(N)으로
입력 수가 커짐에 따라 실행 시간이 비례적으로 증가한다는 것을 알 수 있다.

 

 

그렇다면 효율적인 방법은 뭐가 있을까?

나는 일단 단순하게 자기 자신(number)을 제외하면 모든 약수는 number를 2로 나눈 값보다

작거나 같을 테니 1부터 (number / 2)로 number를 나눴었다.

그러나 다른 사람들의 코드를 분석해본 결과 더 효율적인 방법이 있었다.

√number 보다 작거나 같은 값으로 number를 나눠서

나누어 떨어지면 count를 2번 증가시키면 된다.

그러나 여기서 유의할 점이 있는데,

number를 4라고 가정해보자.

약수는 1, 2, 4로 총 3개의 약수의 개수가 있다.

그러나 위의 알고리즘으로 진행한다면,

√4인 2보다 작거나 같은 값, 1과 2로 4(number)를 나누면

count가 4가 될 것이다.

number를 1이라고 가정했을 때도

약수는 1로 1이 반환이 되어야 하는데, 2가 반환될 것이다.

즉 특정 약수의 제곱(^2) 값이 number와 같은 경우를 예외로 빼야하는 것이다. (count를 1번만 증가하는 걸로)

 

이를 코드로 나타내자면

...

//i * i <= n은 단순히 루트를 취해봐라 i <= √n 을 의미하는 것이다.
for (int i = 1; i * i <= n; i++) { //i는 약수의 경우 수
	
    // i^2이 n이라는 것은 i가 n의 약수라는 것을 내포하고 있음
    if (i * i == n) {
    	count++;
    }
    else if (n % i == 0) {
    	count += 2;
    }
  
    ...

}

...

 

이런 식으로 나타낼 수 있을 것 같다.

특정 약수의 제곱이 number와 같은 경우엔 count를 1번만 해주고, 나머지의 경우엔 2번을 더해주면 된다.

 

 

number의 약수의 절반이 √number 라는 증명은

https://doodle-ns.tistory.com/32

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

이 글을 통해 자세히 볼 수 있다.