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 12 13 14 15 16 17 18 19 20 21 22 Next >

	Amit Dhanuka: 2014-04-11 11:56:53 I don't know why my solution is giving TLE as the same solutionn is accepted in codechef : <snip> Last edit: 2023-03-08 17:56:18
	Navkamal Rakra: 2014-04-10 11:43:05 TLE :(
	Richa Jain: 2013-12-27 12:50:32 Getting TLE again and again, though i have replaced cin and cout with printf and scanf and its O(t*sqrt(n)), any idea??
	Shreyans: 2013-11-13 13:27:11 Last edit: 2013-11-15 10:50:06
	numerix: 2013-11-04 22:20:45 @sud (and some others that still try): There is no "problem" solving it with Python, but you need some knowledge about how to speed up your Python code. Until now there is only one AC Python 3.2 solution and only one visible Python 2.7 solution in the ranklist, that does NOT use psyco (which is no longer available). So, it IS possible with Python 2.7/3.2, but not easily done.
	Sudarshan K: 2013-10-18 11:44:21 getting time limit exceeded in python 3.3.2...?? anybody else having problms with python 3.???
	Orkhan Hasanli: 2013-09-13 02:15:46 What's wrong? I'm pretty sure of my code, this is the easiest question I have ever seen. Why wrong answer? I tested my code with tons of inputs.
	Mitch Schwartz: 2013-08-10 00:14:13 @Avinash Thakur: Click on "compilation error" to read the error...
	Avinash Thakur: 2013-08-09 23:54:51 why am i getting a compilation error although it is running in my system. language used-: java
	coding_express: 2013-07-20 11:01:52 please post the hint for best solution my email id: <snip> Last edit: 2023-03-08 17:58:15

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