N의 약수 찾기 알고리즘

N의 약수를 찾을 때, 1 ~ N까지 모두 탐색하며 나머지가 0일 때를 찾게 되면 시간 초과를 피하기 어렵다.

이때 사용할 수 있는 방법은 두 가지가 있는데, 소인수 분해를 이용해 약수의 개수를 계산하거나 범위를 N의 제곱근으로 좁히는 것이다.

 

소인수 분해를 이용하는 방법

N을 소인수분해하여 각 소수의 지수를 구한 후, 각 지수에 1을 더한 값들을 곱한 후 1을 더하면 약수의 개수를 찾을 수 있다.

N이 24일 때, 이를 소인수 분해하면 2^3 * 3^1 이며 각 지수에 1을 더한 뒤 곱하면 (3 + 1) * (1 + 1) = 8로 약수의 개수를 구할 수 있다.

 

N의 제곱근으로 범위를 좁혀 탐색

N이 24일 때 소수는 1, 2, 3, 4, 6, 8, 12, 24이고 24의 제곱근은 약 4.9이다. 1에서 4까지만 탐색해도 1 * 24, 2 * 12, 3 * 8, 4 * 6 이므로 약수가 8개인 것을 알 수 있다.

 

N이 다른 수의 제곱일 경우, 예를 들어 16 이라면 제곱근은 4이다.

1, 2, 4, 8, 16이 약수이며 1 * 16, 2 * 8, 4 * 4로 도출이 가능하다. 

 

위 두 경우를 고려하여 N % i == 0 일 때 count에 2를 더하고, N / i == i 인 경우에 count를 1 빼는 식으로 함수를 짠다면 시간을 줄일 수 있다.

 

탐색 범위를 1부터 N까지가 아닌 N의 제곱근 만큼만 탐색하는 방식은 N이 소수인지 판별하는 경우에도 탐색 시간을 줄이기 위해 자주 쓰이는 방식이니 참고하면 좋다.