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.