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
nishat_69:
20220205 19:16:57
Be careful about the corner case of input n=1;It has no proper divisor. 

mahbubkuet08:
20211101 19:24:53
AC with Naive solution to calculate sum of divs for each input. 

mars_coder:
20211020 18:18:12
Pre calculation can be an optimization. 

istiak7_:
20210926 13:11:17
why showing "wrong answer edit ideone it....Standard input is empty" after submission? Last edit: 20210926 13:18:08 

upstriver:
20210905 18:58:43
AC in 1 Go


rangey_18o3_20:
20210726 21:14:35
A clue to anyone unable to see why a sieve won't work


jainnamah:
20210719 21:34:31
sum of GP + Fast Expo + sieve (to pre calculate primes) 

rapiram31:
20210623 20:05:51
preprocess using sieve : ) 0.3ms 

trantheba0:
20210615 06:48:30
nlogn trick without any factorization. Time: 0.04 Last edit: 20210615 06:50:08 

hemang_ranga:
20210426 17:16:29
how to check the code

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