[알고리즘] 약수의 개수 구하기

어떤 수 number의 약수의 개수를 구하는 방법은 

1차원적으로 1부터 number까지 나눠서 0이 나오는 것이 약수이다.

 

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

 

그런데 1부터 number까지 루프를 돌아야하므로 number이 커질수록 시간이 무지막지하게 늘어난다.

이를 개선하는 방법은 다른 약수를 이용하는 것이다.

약수는 자신을 곱해서 number가 되는 것 제외하과는 모두 쌍으로 묶어져있다.

 

예를 들어보면 number이 8이라고 하자.

맨처음 약수 1은 맨 뒤 약수 8과 묶여 곱하면 8이 된다.

그 다음 약수 2는 맨 뒤에서 하나 전 약수 4와 묶여 마찬가지로 곱하면 8이 된다.

이렇게 약수 개수가 짝수라면 모두 세트로 묶여있고

홀수라면 자기자신을 두번 곱해서 number가 되는 외톨이 약수가 하나 있는 것이다.

 

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

 

코드로 표현하면 위처럼 되고 i*i가 number보다 작을 때까지만 순회하면 된다.