DIVSUM - Divisor Summation


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

Warning: large Input/Output data, be careful with certain languages


hide comments
Monkey D. Luffy : 2013-04-15 15:57:39

For extra efficiency, remember that divisors come in pairs. For example, if 2 is a divisor of 20 then so is 20/2 = 10.

StupidGuy: 2013-04-15 15:57:39

Finally ACC..But still bad Time...:(

Those with TLE, try printf scanf...it really improves time.
Also sqrt() is faster than i*i

Last edit: 2012-07-08 12:23:53
Kartik Godawat: 2013-04-15 15:57:39

Please help. Tried every possible way for removing TLE. Computation done in <500ms for all inputs at local machine(every no <500000). Using Java BufferedReader.

nani: 2013-04-15 15:57:39

why would i get runtime error??

vinodh reddy velemineti: 2013-04-15 15:57:39

can any ne help me how to ramove it

vinodh reddy velemineti: 2013-04-15 15:57:39

i am getting time limit exceede error

vishal chaudhary: 2013-04-15 15:57:39

@Anup..its because 'scanf' and 'printf' in 'C' are 2-3 times faster than 'cin' and 'cout' in c++ ...thereby reducing the run time and increasing its efficiency which is important for the spoj problems to be accepted...:)

krishna_0507: 2013-04-15 15:57:39

i din't understand how is this spoj compiler working.....when m doing this ques in c++ with an algo it shows me time-limit exceeded .......bt after 3 hrs when i replaced that same file in c replacing just cout's and cin's with printf's and scanf's it accepts my solution .....without any prior change to my rest of the code......can anyone plzzz tell me the reason why is this happening???????thanks in advance...

napster: 2013-04-15 15:57:39

finally...:)

its in the code !: 2013-04-15 15:57:39

what should i do to avoid 'time limit exceeded'?


Added by:Neal Zane
Date:2004-06-10
Time limit:3s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Neal Zane