Summing Divisors

Question

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<stdio.h>
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;
}

• dbasnett: The loop doesn't need to check for values of j > num / 2.
• Shubham Sharma: i did that still spoj is telling time limit exceeded
• rolfl: @dbasnett - even num/2 is too many. It does not need to check past \$\sqrt{num}\$
• dbasnett: @rolfl - this is checking divisors so it is num / 2. Look at the example above using 20.

Answer 1

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 <stdio.h>
#include <math.h>
unsigned long sumDivisors(unsigned long number)
{
 if (number <= 1)
 { 
 return number;
 }
 // start sum at 1, and then loop from 2 later to exclude the number itself.
 // use unsigned long
 unsigned long sum = 1;
 unsigned long root = (unsigned long)sqrt((double)number);
 for(unsigned long divisor = 2; divisor <= root; divisor++)
 { 
 int remainder = number % divisor;
 if(remainder == 0)
 { 
 unsigned long high = number / divisor;
 sum += divisor;
 if (high != divisor)
 { 
 // only add high when the number is not a square number.
 sum += high;
 }
 }
 }
 return sum;
}
int main()
{
 unsigned long problem_count;
 //printf("Enter the number of test_cases");
 scanf("%ul", &problem_count);
 while(--problem_count >= 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;
}

Answer 2

Some optimization jumping right into my mind would be the following thoughts:

• Let's assume you've got the number n.
• When you're looking for integer divisors a, you'll start at 1.
• You're essentially solving b = n / a and check whether b is an integer.
• Using the rule of three, this may be rewritten as n = a * b.
• Due to this, you can assume that once b is smaller than a, you'll only get divisors ́a ́, which you've already seen as b before.
• So if you've found a to be a valid result, b is a valid result as well and once b is smaller than a, you may quit, since you'll have all your results.

Answer 3

You do not have to check every successive numbers for divisibility, you can limit the upper limit to num/currentKnownMaxDivisor.

#include<stdio.h>
int main(){
 int n=56;
 int sum=1+n;// 1 and n are always divisible
 int upperLimit=n;
 int i=2;
 for(;i<upperLimit;i++){
 if( !(n%i)){
 upperLimit= n/i;
 sum += i+ upperLimit;
 // printf(" i=%d u=%d",i,upperLimit); 
 }
 }
 printf("\nsum is %d",sum);
 return 0;
}

Answer 4

A mathematical insight to help you. The Sum of all factors of a number is can be calculated based on the prime factorization. Where the number \$ N \$ can be expressed as the product of prime factors:

$$ \begin{align} \text{if: }N & = a^p \times b^q \times \dots \\ \\ \text{where: }(a,b,...) & \in 2,3,5,7,... (\text{Prime numbers}) \\ \\ \text{then: }S(N) & = \frac{a^{p + 1} - 1}{a-1} \times \frac{b^{q + 1} - 1}{b-1} \times \dots \\ S'(N) & = S(N) - N \\ \end{align} $$

Working this out for \$N = 20\$

$$ \begin{align} N & = 2^2 \times 5^1 \\ \\ S(N) & = \frac{2^{2 + 1} - 1}{2-1} \times \frac{5^{1 + 1} - 1}{5-1}\\ & = \frac{7}{1} \times \frac{24}{4} \\ & = 7 \times 6 \\ & = 42 \\ \\ S'(N) & = 42 - 20\\ & = 22 \\ \end{align} $$

Source: Sum of Divisors from MathsChallenge.net

So, the process is to :

• Generate all the prime numbers below 500000 ,i.e run a loop upto 707 and get all the prime numbers.
• Read the input number of test cases.
• For each test case read, say N, run a loop upto its max prime factor, i.e sqrt(N) <= Prime_Factor_Array[i] and apply the above formula.

• rolfl: This is interesting, but you are not accounting for the time taken to compute the prime factorization thougg.
• thepace: You have around 1-200000 test cases to execute. First compute all the primes < 500000 i.e running a loop upto 707. Once you are done, for each N you will have to run the loop for a limited number of prime numbers.Super fast for multiple test cases. Not so for one.Agreed :)
• rolfl: So you can amortize the cost of the calculation of prime numbers, but you still need to prime-factor the number for each test case... right? Am I missing something?
• rolfl: You are right, you should update your answer to incorporate your comments here.