Summing Divisors

Definition: A proper divisor of a natural number is the divisor that
is strictly less than the number.


e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor
summation is: 1 + 2 + 4 + 5 + 10 = 22.


Input


An integer stating the number of test cases (equal to about 200000),
and that many lines follow, each containing one integer between 1 and
500000 inclusive.


Output


One integer each line: the divisor summation of the integer given
respectively.


Example


Sample Input:

3
2
10
20

Sample Output:

1
8
22

I submitted this problem on spoj and it is telling that time limit exceeded, how to decrease time?

#include
int main()
{
    int num,divisor,sum,i,j,test_cases;
    //printf("Enter the number of test_cases");
    scanf("%d",&test_cases);
    for(i=0;i<test_cases;i++)
    {
        sum=0;
      //  printf("Enter the numbers");
        scanf("%d",&num);
        for(j=1;j<num;j++)
        {
            divisor=num%j;
            if(divisor==0)
            {
                sum=sum+j;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

There are a few comments on this already, but I really want to point out a few things here.

Single responsibility

Loading all the functionality in to the main method is making your code hard to read, and reuse. You should isolate logic in to separate methods whenever you can. In this case, the user-input and the actual sum calculation should be in different places.

Variables

Your naming for values is poor. Each variable (apart from sum) has a problem:

int num,divisor,sum,i,j,test_cases;

• num should be number. Why abbreviate it?

• divisor is misleading. When you do division, you take the dividend, divide it by the divisor, and the result is the quotient. The quotient has a whole part, and a remainder. What you call the divisor is actually the remainder. What you call j is actually the divisor.

• i - not a bad name for a loop variable (test cases), but I would go with something more meaningful, like problem, but, then again, you only use it as the control variable for a loop, and really you can replace the for-loop with a while-loop.

• j - already covered this, it should be divisor (and divisor should be something else.

• test_cases - you are not running tests. You are solving problems. Call it what it is: problem_count.

In addition, variables should be declared where they are used. pre-declaring all variables at the top of a function is a requirement of old versions of C (from last century), and you should be doing better.

Precision

You have declared your variables as int. This could be a problem for systems where int is just 16 bits. You need to store the values up to 5000000, and this requires at least 32 bits. A long is required, and keeping it unsigned would be fine.

Style

You do not have enough white-space in your code. Also called breathing room, or suffocation:

int main() {
    int num,divisor,sum,i,j,test_cases;
    //printf("Enter the number of test_cases");
    scanf("%d",&test_cases);
    for(i=0;i<test_cases;i++)
    {
        sum=0;

What can't that be written as:

int main()
{
    int num, divisor, sum, i, j, test_cases;
    //printf("Enter the number of test_cases");
    scanf("%d", &test_cases);
    for(i = 0; i < test_cases; i++)
    {
        sum = 0;

etc.

Performance

Your code loops for divisors from 1 to just less than num. There is no need to loop this far. Each time you find a factor for your number, you actually find 2, the low, and high parts of the factor. If you loop to the square root of the number, then that's all you need to do, except, for each factor less than the root, you also find one larger than the root. The exception is if the root of the number is also a factor.... then that only counts as one factor, not two.

So, for example, the input 20. The square-root of 20 is 4.47... We know:

• 1 is the first factor of 20

• 2 is a factor (and 20 / 2 is 10, which is the high factor).

• 3 is not a factor

• 4 is a factor (and 20 / 4 is 5, which is the high factor).

• 5 is larger than 4.47... so we stop at there.

Our factors for 20 are thus 1, 2, 10, 4, 5, and 20 itself.

The rules for this challenge exclude the number itself, so 20 is not part of it.

The sum of factors is thus: 1 + 2 + 4 + 5 + 10 = 22

In order to find all factors, you only need to loop through to \$\sqrt{num}\$, and you need special handling for the input value 1, and when the root itself is an exact factor of the number.

Conclusion

Putting this all together, I propose the following:

#include 
#include 

unsigned long sumDivisors(unsigned long number)
{
    if (number = 0)
    {  
        unsigned long number = 0;
      //  printf("Enter the numbers");
        scanf("%lu", &number);

        unsigned long sum = sumDivisors(number);

        //printf("%lu -> %lu\n", number, sum);
        printf("%lu\n", sum);
    }
    return 0;
}

StackExchange Code Review Q#73445, answer score: 7