HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Find number of divisors for integer and sum of integers

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sumnumberfordivisorsfindandintegersinteger

Problem

-
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;
}


-
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.)

Solution

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.

Context

StackExchange Code Review Q#2378, answer score: 4

Revisions (0)

No revisions yet.