SPOJ.com - Problem DIVSUM

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

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

Submit solution!

hide comments

< Previous 10 11 12 13 14 15 16 17 18 19 20 Next >

	Abhinandan Agarwal: 2015-02-22 22:25:53 Small puny mistakes willl take me down someday ...
	Mahesh Kohli: 2015-02-21 15:03:21 should the answer be 0 for n=1?
	sarvagya: 2015-02-17 16:14:46 time limit exceeded :(
	Himanshu: 2015-02-11 07:44:32 make your own power function. the pow function in maths library rounds down when converting to integer. eg pow(5,2) will be returned as 24.
	Phạm Bãng Bãng: 2015-01-18 12:58:49 n <= 100000 and AC :D --Francky--> (Shocked) It's true and we have too n<33333 !!! Last edit: 2015-01-18 13:32:40
	Minsuk Kim: 2014-11-27 02:01:41 Python 2.7 novice here - keep on getting time limit exceeded although my code works perfectly fine. I have tried many test cases... --ans(Francky)--> It's not easy with Python, you can see there's few AC with Python. With cube cluster, now, it's easier than with Pyramid as the time limit is more relax. Last edit: 2014-11-27 02:18:55
	Vikas: 2014-10-24 06:28:21 Solved in just 0.24s. Nice Problem .
	mehmetin: 2014-10-08 14:08:14 Can the time limit be reduced for problems that have been changed to cube cluster? For this problem, it could be 1s or 0.5 s.
	Mitch Schwartz: 2014-10-07 13:59:34 :( I wrote to an admin about the mass change of many problems from Pyramid to Cube, it's very worrying. The current Python results for this problem are also curious, with high memory and 0.00s time. I checked that psyco isn't available. There might be some bug there. Last edit: 2014-10-07 14:49:21
	Ujjwal Kumar Singh: 2014-08-01 10:17:37 he guys i am a newbie here i know just basic c++ things getting SIGSEGV error on spoj however code working fine in codeblocks application helpp plz <snip> Last edit: 2023-03-08 17:56:08

Submit solution!

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