SPOJ DIVSUM - Divisor Summation

Question

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
 {
 BufferedReader BR=new BufferedReader(new InputStreamReader(System.in));
 int t,i,j;
 t=Integer.parseInt(BR.readLine());
 int a[]=new int [t];
 int sum[]=new int [t];
 for(i=0;i<t;i++)
 {
 a[i]=Integer.parseInt(BR.readLine());
 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?

• bdean20: See related: codereview.stackexchange.com/questions/109397/… Given your algorithm is roughly the same as theirs, it appears the insight you are missing relates to the symmetry of divisors. Your innermost loop can be restructured so it only needs to go to sqrt(a[i]) and you get 2 divisors out of each positive check.
• chia yongkang: Another way would be to make use of the number theory. References : mathschallenge.net/library/number/sum_of_divisors

Answer 1

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)

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