7
\$\begingroup\$
  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.)

\$\endgroup\$
4
  • \$\begingroup\$ I believe the formatting was messed up a bit due to the numberings in your question, adding some extra spacing seemed to have solved it. \$\endgroup\$ May 12, 2011 at 9:35
  • \$\begingroup\$ @Steven: Thanks. Yes i tried but couldn't fix it. \$\endgroup\$
    – goldenmean
    May 12, 2011 at 10:14
  • \$\begingroup\$ You should give some context for the second function. From the code it looks to me as if you're iterating from 0 to some number N and on each iteration calling next_no with the current index and the result from the last call of next_no. So you're basically calculating the sum from 0 to idx for each idx from 0 to N. However for now that's just me guessing, so you should be more specific about that. \$\endgroup\$
    – sepp2k
    May 12, 2011 at 11:22
  • \$\begingroup\$ @sepp2k:Yes, I am computing summation of integers uptox idx for each idx passed in. And this function can be called with idx value possibly from 0 to ULLONG_MAX. \$\endgroup\$
    – goldenmean
    May 12, 2011 at 11:28

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ The first change may not be appropriate - if he really wants all the divisors (not just prime factors) then I think his way is the only way to do it. \$\endgroup\$
    – DHall
    May 12, 2011 at 13:00
  • \$\begingroup\$ @DHall: Can you give an example where the algorithm I outlined would not give the correct number of divisors? It definitely does not return the number of prime factors. \$\endgroup\$
    – sepp2k
    May 12, 2011 at 13:11
  • 1
    \$\begingroup\$ Sorry, I misread it. Your way is correct. \$\endgroup\$
    – DHall
    May 12, 2011 at 13:15
  • \$\begingroup\$ Edited my OP. Can u pls. check OP again and see if this code incorporates the optimizations correctly. \$\endgroup\$
    – goldenmean
    May 12, 2011 at 14:15
2
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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