Finding the number of divisors of an integer

Question

I need to find the number of divisors of an integer(n) for a problem in codechef. I have written the following program to compute the number of divisors. But the program is exceeding the time limit. Is there any way to optimize my approach to this problem?Can you suggest a faster algorithm?

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
 int n,i=1,d=0;
        while(i<=sqrt(n))
         {
          if(n%i==0)
           {
            d++;
             if(i!=(n/i))
              d++;
           }
          i++; 
         }
   cout<<d;

Start here: https://www.google.com/search?num=100&q=number+of+divisors — n. m. could be an AI, Feb 04 '16 at 18:39
When you do int n,i=1,d=0; your n and i are both 1 so i in while(i<=sqrt(n)) is never les than the square root of 1. That's why it never stops. — Atirag, Feb 04 '16 at 18:49

score 0 · Answer 1 · edited May 23 '17 at 11:58

As far as I understood, you just need number of divisors. Find all the prime divisors and write the x1^a1 * x2^a2 ... * xn^an. The number of divisors equal to (a1+1)*(a2+1)*...*(an+1)

For example, 12=2^2*3^1, therefore, it has (2+1)*(1+1) = 6 divisors, i.e. 1,2,3,4,6,12. I didn't test the code but it should work.

int main()
{
     int n,i=2,d=0;
     int num_div = 1;
     while(i <= sqrt(n))
     {
         int cnt = 0;
         while(n % i == 0){
             cnt++;
             n /= i;
         }                 
         if (cnt != 0)
             num_div *= (cnt+1);
         i++; 
     }
     cout<<num_div;
}

Check this answer

Finding the number of divisors of an integer

1 Answers1