1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – bdean20 May 19 '16 at 6:10
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.