Last Updated: 11 Dec, 2020
Sum Of Proper Divisors
Easy
Asked in companies
Given a natural number 'N', return the sum of all proper divisors of ‘N’.
‘X’ is a proper divisor of ‘Y’ if X < Y and Y % X = 0.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases . Then each test case follows.
The first line of each testcase contains a single integer ‘N’.
Output Format :
For each test case print a single integer denoting the sum of all proper divisors of ‘N’.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^9
Time limit: 1 sec
Approaches
For the given N, simply iterate numbers from 1 to N-1 and if the number is divisible by N, then simply add it to the final answer.
The steps are as follows:
- Initialize sum = 0
- Run a for loop from 1 to N - 1, if the number is divisible by N simply add it to ‘sum’.
- Return sum after iterating all elements less than N.
For the given N simply run a for loop for X belonging to 1 to square root of N, if X is divisible by N we will add X and N / X to our answer. Just make sure to not add the value if it is equal to N, also to not double count the value when X = N / X.
The steps are as follows:
- Initialize sum = 0
- Run a for loop for X from 1 to sqrt(N), if X is divisible by N simply add X and N / X to the ‘sum’.
- If X = N or N / X = N don’t add it to Ans.
- If X = N / X only add X to the Ans.
- Return sum.