2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Oct 14 '15 at 4:41
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 17 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.