Algorithm

Problem link- https://www.spoj.com/problems/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

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

MAX = 500005
sigma = [0] * MAX
lp = [0] * MAX
p = [0] * MAX
pc = [0] * MAX

for i in range(2, MAX):
    if lp[i] == 0:
        for j in range(i, MAX, i):
            if lp[j] == 0:
                lp[j] = i
sigma[1] = 1
for i in range(2, MAX):
    j = i / lp[i]
    if j % lp[i] == 0:
        p[i] = p[j]
        pc[i] = pc[j] * lp[i]
    else:
        p[i] = j
        pc[i] = lp[i]
    sigma[i] = sigma[p[i]] * (pc[i] * lp[i] - 1) / (lp[i] - 1)
T = int(input())
for _ in range(T):
    N = int(input())
    print(sigma[N] - N)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
2
10
20

Output

x
–
+
cmd
1
8
22

#2 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>

using namespace std;

int main(){    
    int t,n,i;
    int S;
    
    scanf("%d",&t);
    
    for(int tc=1;tc<=t;tc++){
        scanf("%d",&n);
        
        S=0;
        
        for(i=1;i*i<n;i++)
            if(n%i==0)
                S+=i+n/i;
        
        if(i*i==n) S+=i;
        S-=n;
        
        printf("%d\n",S);
    }   
    
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
2
10
20

Output

x
–
+
cmd
1
8
22
Advertisements

Demonstration

SPOJ Solution-Divisor Summation-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python