Sum of all proper divisors of a natural number
Given a natural number, calculate sum of all its proper divisors. A proper divisor of a natural number is the divisor that is strictly less than the number.
For example, number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.
Examples :
Input : num = 10 Output: 8 // proper divisors 1 + 2 + 5 = 8 Input : num = 36 Output: 55 // proper divisors 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55
This problem has very simple solution, we all know that for any number ‘num’ all its divisors are always less than and equal to ‘num/2’ and all prime factors are always less than and equal to sqrt(num). So we iterate through ‘i’ till i<=sqrt(num) and for any ‘i’ if it divides ‘num’ , then we get two divisors ‘i’ and ‘num/i’ , continuously add these divisors but for some numbers divisors ‘i’ and ‘num/i’ will same in this case just add only one divisor , e.g; num=36 so for i=6 we will get (num/i)=6 , that’s why we will at 6 in the summation only once. Finally we add one as one is divisor of all natural numbers.
C++
// C++ program to find sum of all divisors of // a natural number #include<bits/stdc++.h> using namespace std; // Function to calculate sum of all proper divisors // num --> given natural number int divSum( int num) { // Final result of summation of divisors int result = 0; if (num == 1) // there will be no proper divisor return result; // find all divisors which divides 'num' for ( int i=2; i<= sqrt (num); i++) { // if 'i' is divisor of 'num' if (num%i==0) { // if both divisors are same then add // it only once else add both if (i==(num/i)) result += i; else result += (i + num/i); } } // Add 1 to the result as 1 is also a divisor return (result + 1); } // Driver program to run the case int main() { int num = 36; cout << divSum(num); return 0; } |
Java
// JAVA program to find sum of all divisors // of a natural number import java.math.*; class GFG { // Function to calculate sum of all proper // divisors num --> given natural number static int divSum( int num) { // Final result of summation of divisors int result = 0 ; // find all divisors which divides 'num' for ( int i = 2 ; i <= Math.sqrt(num); i++) { // if 'i' is divisor of 'num' if (num % i == 0 ) { // if both divisors are same then // add it only once else add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as 1 is also // a divisor return (result + 1 ); } // Driver program to run the case public static void main(String[] args) { int num = 36 ; System.out.println(divSum(num)); } } /*This code is contributed by Nikita Tiwari*/ |
Python3
# PYTHON program to find sum of all # divisors of a natural number import math # Function to calculate sum of all proper # divisors num --> given natural number def divSum(num) : # Final result of summation of divisors result = 0 # find all divisors which divides 'num' i = 2 while i< = (math.sqrt(num)) : # if 'i' is divisor of 'num' if (num % i = = 0 ) : # if both divisors are same then # add it only once else add both if (i = = (num / i)) : result = result + i; else : result = result + (i + num / i); i = i + 1 # Add 1 to the result as 1 is also # a divisor return (result + 1 ); # Driver program to run the case num = 36 print (divSum(num)) # This code is contributed by Nikita Tiwari |
C#
// C# program to find sum of all // divisorsof a natural number using System; class GFG { // Function to calculate sum of all proper // divisors num --> given natural number static int divSum( int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for ( int i = 2; i <= Math.Sqrt(num); i++) { // if 'i' is divisor of 'num' if (num % i == 0) { // if both divisors are same then // add it only once else add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as 1 // is also a divisor return (result + 1); } // Driver Code public static void Main() { int num = 36; Console.Write(divSum(num)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to find sum of // all divisors of a natural number // Function to calculate sum of // all proper divisors // num --> given natural number function divSum( $num ) { // Final result of // summation of divisors $result = 0; // find all divisors // which divides 'num' for ( $i = 2; $i <= sqrt( $num ); $i ++) { // if 'i' is divisor of 'num' if ( $num % $i == 0) { // if both divisors are // same then add it only // once else add both if ( $i == ( $num / $i )) $result += $i ; else $result += ( $i + $num / $i ); } } // Add 1 to the result as // 1 is also a divisor return ( $result + 1); } // Driver Code $num = 36; echo (divSum( $num )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find sum of all divisors of // a natural number // Function to calculate sum of all proper divisors // num --> given natural number function divSum(num) { // Final result of summation of divisors let result = 0; // find all divisors which divides 'num' for (let i=2; i<=Math.sqrt(num); i++) { // if 'i' is divisor of 'num' if (num%i==0) { // if both divisors are same then add // it only once else add both if (i==(num/i)) result += i; else result += (i + num/i); } } // Add 1 to the result as 1 is also a divisor return (result + 1); } // Driver program to run the case let num = 36; document.write(divSum(num)); // This code is contributed by Mayank Tyagi </script> |
Output :
55
Time Complexity: O(?n)
Auxiliary Space: O(1)
Please refer below post for an optimized solution and formula.
Efficient solution for sum of all the factors of a number
Contact Us