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?

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)