Sum of common divisors of two numbers A and B
Given two number A and B, the task is to find the sum of common factors of two numbers A and B. The numbers A and B is less than 10^8.
Examples:
Input: A = 10, B = 15 Output: Sum = 6 The common factors are 1, 5, so their sum is 6 Input: A = 100, B = 150 Output: Sum = 93
Naive Approach: Iterate from i = 1 to minimum of A and B and check whether i is a factor of both A and B. If i is a factor of A and B then add it to sum. Display the sum at the end of the loop.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // print the sum of common factors int sum( int a, int b) { // sum of common factors int sum = 0; // iterate from 1 to minimum of a and b for ( int i = 1; i <= min(a, b); i++) // if i is the common factor // of both the numbers if (a % i == 0 && b % i == 0) sum += i; return sum; } // Driver code int main() { int A = 10, B = 15; // print the sum of common factors cout << "Sum = " << sum(A, B) << endl; return 0; } |
Java
// Java implementation of above approach import java.io.*; class GFG { // print the sum of common factors static int sum( int a, int b) { // sum of common factors int sum = 0 ; // iterate from 1 to minimum of a and b for ( int i = 1 ; i <= Math.min(a, b); i++) // if i is the common factor // of both the numbers if (a % i == 0 && b % i == 0 ) sum += i; return sum; } // Driver code public static void main (String[] args) { int A = 10 , B = 15 ; // print the sum of common factors System.out.print( "Sum = " + sum(A, B)); } } // This code is contributed by shs.. |
Python 3
# Python 3 implementation of # above approach # print the sum of common factors def sum (a, b): # sum of common factors sum = 0 # iterate from 1 to minimum of a and b for i in range ( 1 , min (a, b)): # if i is the common factor # of both the numbers if (a % i = = 0 and b % i = = 0 ): sum + = i return sum # Driver Code A = 10 B = 15 # print the sum of common factors print ( "Sum =" , sum (A, B)) # This code is contributed # by Akanksha Rai |
C#
// C# implementation of above approach using System; class GFG { // print the sum of common factors static int sum( int a, int b) { // sum of common factors int sum = 0; // iterate from 1 to minimum of a and b for ( int i = 1; i <= Math.Min(a, b); i++) // if i is the common factor // of both the numbers if (a % i == 0 && b % i == 0) sum += i; return sum; } // Driver code public static void Main () { int A = 10, B = 15; // print the sum of common factors Console.WriteLine( "Sum = " + sum(A, B)); } } // This code is contributed by shs.. |
PHP
<?php // PHP implementation of above approach // print the sum of common factors function sum( $a , $b ) { // sum of common factors $sum = 0; // iterate from 1 to minimum of a and b for ( $i = 1; $i <= min( $a , $b ); $i ++) // if i is the common factor // of both the numbers if ( $a % $i == 0 && $b % $i == 0) $sum += $i ; return $sum ; } // Driver code $A = 10; $B = 15; // print the sum of common factors echo "Sum = " , sum( $A , $B ); // This code is contributed by shs. ?> |
Javascript
<script> // Javascript implementation of above approach // print the sum of common factors function sum(a, b) { // sum of common factors var sum = 0; // iterate from 1 to minimum of a and b for ( var i = 1; i <= Math.min(a, b); i++) // if i is the common factor // of both the numbers if (a % i == 0 && b % i == 0) sum += i; return sum; } var A = 10, B = 15; // print the sum of common factors document.write( "Sum = " + sum(A, B) + "<br>" ); //This code is contributed by SoumikMondal </script> |
Output:
Sum = 6
Time Complexity: O(min(a, b))
Auxiliary Space: O(1)
An efficient approach is to use the same concept used in Common divisors of two numbers. Calculate the greatest common divisor (gcd) of given two numbers, and then find the sum of divisors of that gcd.
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to calculate gcd of two numbers int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate all common divisors // of two given numbers // a, b --> input integer numbers int sumcommDiv( int a, int b) { // find gcd of a, b int n = gcd(a, b); // Find the sum of divisors of n. int sum = 0; for ( int i = 1; i <= sqrt (n); i++) { // if 'i' is factor of n if (n % i == 0) { // check if divisors are equal if (n / i == i) sum += i; else sum += (n / i) + i; } } return sum; } // Driver program to run the case int main() { int a = 10, b = 15; cout << "Sum = " << sumcommDiv(a, b); return 0; } |
Java
//Java implementation of above approach import java.io.*; class GFG { // Function to calculate gcd of two numbers static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b % a, a); } // Function to calculate all common divisors // of two given numbers // a, b --> input integer numbers static int sumcommDiv( int a, int b) { // find gcd of a, b int n = gcd(a, b); // Find the sum of divisors of n. int sum = 0 ; for ( int i = 1 ; i <= Math.sqrt(n); i++) { // if 'i' is factor of n if (n % i == 0 ) { // check if divisors are equal if (n / i == i) sum += i; else sum += (n / i) + i; } } return sum; } // Driver program to run the case public static void main (String[] args) { int a = 10 , b = 15 ; System.out.println( "Sum = " + sumcommDiv(a, b)); } } |
Python3
# Python 3 implementation of above approach from math import gcd,sqrt # Function to calculate all common divisors # of two given numbers # a, b --> input integer numbers def sumcommDiv(a, b): # find gcd of a, b n = gcd(a, b) # Find the sum of divisors of n. sum = 0 N = int (sqrt(n)) + 1 for i in range ( 1 ,N, 1 ): # if 'i' is factor of n if (n % i = = 0 ): # check if divisors are equal if (n / i = = i): sum + = i else : sum + = (n / i) + i return sum # Driver program to run the case if __name__ = = '__main__' : a = 10 b = 15 print ( "Sum =" , int (sumcommDiv(a, b))) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of above approach using System; public class GFG{ // Function to calculate gcd of two numbers static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate all common divisors // of two given numbers // a, b --> input integer numbers static int sumcommDiv( int a, int b) { // find gcd of a, b int n = gcd(a, b); // Find the sum of divisors of n. int sum = 0; for ( int i = 1; i <= Math.Sqrt(n); i++) { // if 'i' is factor of n if (n % i == 0) { // check if divisors are equal if (n / i == i) sum += i; else sum += (n / i) + i; } } return sum; } // Driver program to run the case static public void Main (){ int a = 10, b = 15; Console.WriteLine( "Sum = " + sumcommDiv(a, b)); } } |
PHP
<?php // PHP implementation of above approach // Function to calculate gcd of two numbers function gcd( $a , $b ) { if ( $a == 0) return $b ; return gcd( $b % $a , $a ); } // Function to calculate all common divisors // of two given numbers // a, b --> input integer numbers function sumcommDiv( $a , $b ) { // find gcd of a, b $n = gcd( $a , $b ); // Find the sum of divisors of n. $sum = 0; for ( $i = 1; $i <= sqrt( $n ); $i ++) { // if 'i' is factor of n if ( $n % $i == 0) { // check if divisors are equal if ( $n / $i == $i ) $sum += $i ; else $sum += ( $n / $i ) + $i ; } } return $sum ; } // Driver program to run the case $a = 10; $b = 15; echo "Sum = " , sumcommDiv( $a , $b ); ?> |
Javascript
<script> // Javascript implementation of above approach // Function to calculate gcd of two numbers function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate all common divisors // of two given numbers // a, b --> input integer numbers function sumcommDiv(a, b) { // find gcd of a, b var n = gcd(a, b); // Find the sum of divisors of n. var sum = 0; for ( var i = 1; i <= Math.sqrt(n); i++) { // if 'i' is factor of n if (n % i == 0) { // check if divisors are equal if (n / i == i) sum += i; else sum += (n / i) + i; } } return sum; } // Driver program to run the case var a = 10, b = 15; document.write( "Sum = " + sumcommDiv(a, b)); // This code is contributed by rutvik_56. </script> |
Output:
Sum = 6
Time complexity: O(sqrt(n))
Auxiliary Space: O(logn)