# SPOJ DIVSUM - Divisor Summation

DIVSUM - Divisor Summation
#number-theory
Given a natural number n (1 <= n <= 500000), please output the summation of all its proper 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

code:-

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int t,i,j;
int a[]=new int [t];
int sum[]=new int [t];
for(i=0;i<t;i++)
{
sum[i]=0;
for(j=1;j<a[i];j++)
{
if(a[i]%j==0)
sum[i]+=a[j];
}

}

for(i=0;i<t;i++)
{
System.out.println(sum[i]);
}
}
}


I am getting time limit exceeded error for this program from SPOJ. How do I avoid it?

There is a much better solution to your problem. Some mistakes you could have avoided -

• You use 2 loops. One would also do it.

• You iterate all the elements in the nested array. You do not need to include the element itself (as indirectly mentioned in the question). Therefore, you can iterate only a[i]/2 elements.

You can optimize this further also. Here is my code but unfortunately it is in Python. Hope you can at least understand that. It is an easy language.

for i in range(int(input())):
x = int(input())
sum=0
for j in range(x/2):
if(x%j==0):
sum += j
print(sum)

• It's not even necessary to iterate through a[i]/2 elements... – Peter Taylor Sep 24 '18 at 7:23
• Yes, @PeterTaylor The best approach works in O(√x). But this also works. – Daksh Agrawal Sep 24 '18 at 9:07