 # Time complexity for finding the number of divisors of a given number N

I am solving a problem which requires to compute the number of divisors of a given number N. Currently I am using integer prime factorization to obtain the count.

Given a number N:
we can express N as, N = a^p * b^q * c^r . . .

where a, b, c are prime factors of N and
p, q, r are the number of times the respective prime factor divides N.
Then, we have number of divisors = (p + 1) * (q + 1) * (r + 1) * . . .

int divisor_count(long long num) {
long long count = 1, temp_count = 0;

while (num % 2 == 0) {
num /= 2;
++temp_count;
}

count *= (temp_count + 1);

for (long long i = 3; i * i <= num; ++i) {
temp_count = 0;

while (num % i == 0) {
num /= i;
++temp_count;
}

count *= (temp_count + 1);
}

if (num > 2) {
count *= 2;
}

return count;
}


What exactly is the time complexity of this approach and how to prove it?

I don’t think its exactly O(sqrt(N)) as we are dividing N by its prime factor repeatedly.

O(\sqrt(n)*log_{\sqrt(n)}(n))