Find number of divisors for integer and sum of integers

Question

1. This function computes and returns the number of divisors an integer has. But it is very slow and I believe it can be optimized for speed.

   unsigned long long int find_no_of_divisors(unsigned long long int myno,FILE *ifp)
   {
   
       unsigned long long int divsrs = 2;    
       unsigned long long int k = 2;
   
       if(myno == 1)
       {
           return 1;
       }
   
       if(myno == 2)
       {
           return 2;
       }
   
       while(1)
       {
           if((myno % k) == 0)
           {           
               divsrs++;
               if(divsrs == MY_ULLONG_MAX)
               {
                   printf("Overflow detected in the calculated value for divisors of a number... Exiting");
                   fclose(ifp);
                   exit(-1);
               }           
           }
   
           k++;        
   
           if(k > (myno/2))
           {
               break;
           }
       }
   
       return divsrs;
   }
   

2. This one computes and returns the sum of first n integers:

   unsigned long long int next_no(unsigned long long int idx,unsigned long long int cur_no,FILE *ifp)
   {
       unsigned long long int next_no;
   
       next_no = ((idx)*(idx + 1))/2;
   
       if((next_no - idx) != cur_no)
       {
           printf("Overflow detected in the value of the calculated number... Exiting");
           fclose(ifp);
           exit(-1);
       }
       return next_no;
   }
   

Could there be any glitches or functionality issues? (PS - I did not want to use a sqrt() function due to my portability constraints.)

Answer 1

The first function can be sped up by just iterating up to sqrt(myno) and adding 2 instead of 1 to divsrs when k divides myno unless k is the square root of myno (in which case you would only add 1).

The second function already takes constant, but you can get rid of the multiplication and division, by simply returning cur_no + idx and using cur_no < ULLONG_MAX - idx to check whether there'd be an overflow.

---

Now a couple of style notes on the code:

First of all, it seems strange to me to pass the file handle to the functions, if they don't actually write to (or read from) the file. I see that you did so you could close the file before exiting the program in case of an overflow. I would rather recommend that you return an error value when an overflow occurs and then close the file and exit in the calling code.

Further your while(1) loop in find_no_of_divisors is actually a pretty plain for-loop and should be written as one. No need for complicated control flow for something so simple.

Lastly I would not recommend dropping (some) vowels from variable names like you do in divsrs - that just leads to typos.

Answer 2

Additional to sepp2k's excellent answer some math that could help you:

If you have the prime factors of a number, you just take the exponents, increase every one by one and take the product.

E.g. 12 = 2^2 * 3^1 -> [2,1] -(+1)-> [3,2] -> 6
12 has 6 divisors: 1,2,3,4,6,12 

E.g. 100 = 2^2 * 5^2 -> [2,2] -(+1)-> [3,3] -> 9
100 has 9 divisors: 1,2,4,5,10,20,25,50,100

The smallest divisor of a number (greater than 1) is always prime. The algorithm in pseudocode looks like (untested):

divisors(N) {
  result = 1
  for (p = 2; p <= sqrt(N); p++) { //check all divisors
     if (n mod p == 0) {
        for(f = 0; n mod p == 0; n = n / p) { //try to divide as often as possible
           f++  //count how often we divide
        }
        result = result * (f+1)  
     }  
  }
  if (N == 1) return result //number completely factored
  else return 2 //then we found no factor -> N itself is prime 
}