# Determine the number of factors of a large numbers efficiently

I am trying to determine the number of factors of a large number efficiently. I have written this function but how can it be improved upon?

long numOfFactors(long long n)
{
long i=0,num=0;
for(i=1;i<=n/2;i++)
{
if(n%i==0)
num++;
}
return num;
}


Your program actually gives the wrong output for every number. You're forgetting that n is a factor of n! The easy fix is to simply initialize num to 1. Even better to initialize num to 2 and start your loop at i=2. Once you fix that, your program is fine. It's just that you can just do a lot better performance-wise.

Let's start with the general formula. Any number can be expressed as the product of primes raised to some power: $n = \prod_i p_i^{k_i}$. The number of factors of $n$ in this case is $\prod_i(1+k_i)$. So what we need to do is find all the prime factors.

How do we do that? We can actually reduce n as we go. Everytime we find a factor, if we do it right, we can be sure it's prime, so we reduce it as far as possible:

exp = 0;
while (n%i == 0) {
++exp;
n /= i;
}


So if we're doing 80, as an example, we will divide by 2 until we're no longer divisible by 2 (that is, n == 5). All we have to do then is multiply out all the exps:

long numOfFactors(long long n)
{
long num_factors=1;
long i;
long exp;

for(i=2; i*i<=n; ++i)
{
exp=0;
while (n%i == 0) {
++exp;
n /= i;
}
num_factors *= (exp + 1);
}

return num_factors * (n > 1 ? 2 : 1);
}


The last check is there because if n>1 at the end, we know it's prime and we haven't counted it yet, so that's another doubling of factors.

• Question: Is it OK that i is a long, but n is a long long? Will i be promoted to long long or could the condition in the for loop end up in an infinite loop if n is bigger than the max long? Oct 14 '15 at 4:41
• Problems with i*i<=n. i*i can overflow long math. Fixing that to long long i, i*i<=n can lead to signed integer overflow should n be a large prime. i <= n/i is better. The cost of the division is often tied to n%i so code can do both for the same impact. Nov 17 '17 at 22:40