약수의 개수 구하는 방법

숫자 N의 약수의 개수를 구하는 문제가 주어졌을 때,

1부터 N까지 모두 탐색을 하게 되면, N이 100,000같이 크기가 클 경우 시간이 많이 걸린다.

 

 

 

약수 개수를 구할 때, 시간을 줄이는 방법은 2가지가 있다.

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

N을 소인수분해하여 각 소수의 지수를 구한 후, (각 지수+1) 값들을 곱하여 약수의 개수를 구한다.

ex) N이 24일 경우

24 = 2³ * 3¹

→ (3 + 1) * (1 + 1) = 4 * 2 = 8

즉, 24의 약수의 개수는 8이 된다. (1, 2, 3, 4, 6, 8, 12, 24)

 

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

만약 N이 24일 경우, 24의 제곱근(√24)은 4.xxxx이다.

따라서 1~24가 아닌, 1~4까지만 탐색해도

[ 1, 2, 3, 4 | 6, 8, 12, 24 ] 이렇게 약수가 8개인 것을 바로 알 수 있다.

 

만약 N이 다른 수의 제곱일 경우, 16을 예로 들면 제곱근(√16)은 4이다.

따라서 [ 1, 2, 4, 8, 16 ]이 약수이고, 4를 중심으로 양쪽에 약수가 있다.

 

위 경우를 고려하여 다음과 같은 코드를 짤 수 있다.

// N = 24일 경우
let count = 0; //약수개수
let index = 1;
let sqrt = Math.floor(Math.sqrt(24)); //4
while(index <= sqrt) { //1~24가 아닌, 1~4까지
    if(24 % index === 0) { // 24를 1로 나눠떨어지면 
        count = count + 2; // 약수개수를 2개씩 늘린다. 
        if(24/index === index) { //24를 1로 나눠 1이 나오면 약수개수 -1(ex: 16/4=4)
            count = count - 1;
        }
    }
    index++;
}

 

탐색범위를 1~N 전부가 아닌, N의 제곱근까지만 탐색하는 방식은 탐색 시간을 줄이기 위해 자주 쓰인다.

 

 

**출처 : 모든 내용은 프로그래머스 '기사단원의 무기'를 기반으로 작성하였습니다.