Sum of GCD of all numbers upto N with N itself
Given an integer N, the task is to find the sum of Greatest Common Divisors of all numbers up to N with N itself.
Examples:
Input: N = 12
Output: 40
Explanation:
GCD of [1, 12] = 1, [2, 12] = 2, [3, 12] = 3, [4, 12] = 4, [5, 12] = 1, [6, 12] = 6, [7, 12] = 1, [8, 12] = 4, [9, 12] = 3, [10, 12] = 2, [11, 12] = 1, [12, 12] = 12. The sum is (1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12) = 40.
Input: N = 2
Output: 3
Explanation:
GCD of [1, 2] = 1, [2, 2] = 2 and their sum is 3.
Naive Approach: A simple solution is to iterate over all numbers from 1 to N and find their gcd with N itself and keep on adding them.
Time Complexity: O(N * log N)
Efficient Approach:
To optimize the above-mentioned approach, we need to observe that GCD(i, N) gives one of the divisors of N. So, instead of running a loop from 1 to N, we can check for each divisor of N how many numbers are there with GCD(i, N) same as that divisor.
Illustration:
For example N = 12, its divisors are 1, 2, 3, 4, 6, 12.
Numbers in range [1, 12] whose GCD with 12 is:
- 1 are {1, 5, 7, 11}
- 2 are {2, 10}
- 3 are {3, 9}
- 4 are {4, 8}
- 6 is {6}
- 12 is {12}
So answer is; 1*4 + 2*2 + 3*2 + 4*2 + 6*1 + 12*1 = 40.
- So we have to find the number of integers from 1 to N with GCD d, where d is a divisor of N. Let us consider x1, x2, x3, …. xn as the different integers from 1 to N such that their GCD with N is d.
- Since, GCD(xi, N) = d then GCD(xi/d, N/d) = 1
- So, the count of integers from 1 to N whose GCD with N is d is Euler Totient Function of (N/d).
Below is the implementation of the above approach:
C++
// C++ Program to find the Sum // of GCD of all integers up to N // with N itself #include <bits/stdc++.h> using namespace std; // Function to Find Sum of // GCD of each numbers int getCount( int d, int n) { int no = n / d; int result = no; // Consider all prime factors // of no. and subtract their // multiples from result for ( int p = 2; p * p <= no; ++p) { // Check if p is a prime factor if (no % p == 0) { // If yes, then update no // and result while (no % p == 0) no /= p; result -= result / p; } } // If no has a prime factor greater // than sqrt(n) then at-most one such // prime factor exists if (no > 1) result -= result / no; // Return the result return result; } // Finding GCD of pairs int sumOfGCDofPairs( int n) { int res = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { // Calculate the divisors int d1 = i; int d2 = n / i; // Return count of numbers // from 1 to N with GCD d with N res += d1 * getCount(d1, n); // Check if d1 and d2 are // equal then skip this if (d1 != d2) res += d2 * getCount(d2, n); } } return res; } // Driver code int main() { int n = 12; cout << sumOfGCDofPairs(n); return 0; } |
Java
// Java program to find the Sum // of GCD of all integers up to N // with N itself class GFG{ // Function to Find Sum of // GCD of each numbers static int getCount( int d, int n) { int no = n / d; int result = no; // Consider all prime factors // of no. and subtract their // multiples from result for ( int p = 2 ; p * p <= no; ++p) { // Check if p is a prime factor if (no % p == 0 ) { // If yes, then update no // and result while (no % p == 0 ) no /= p; result -= result / p; } } // If no has a prime factor greater // than Math.sqrt(n) then at-most one such // prime factor exists if (no > 1 ) result -= result / no; // Return the result return result; } // Finding GCD of pairs static int sumOfGCDofPairs( int n) { int res = 0 ; for ( int i = 1 ; i * i <= n; i++) { if (n % i == 0 ) { // Calculate the divisors int d1 = i; int d2 = n / i; // Return count of numbers // from 1 to N with GCD d with N res += d1 * getCount(d1, n); // Check if d1 and d2 are // equal then skip this if (d1 != d2) res += d2 * getCount(d2, n); } } return res; } // Driver code public static void main(String[] args) { int n = 12 ; System.out.print(sumOfGCDofPairs(n)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to find the sum # of GCD of all integers up to N # with N itself # Function to Find Sum of # GCD of each numbers def getCount(d, n): no = n / / d; result = no; # Consider all prime factors # of no. and subtract their # multiples from result for p in range ( 2 , int ( pow (no, 1 / 2 )) + 1 ): # Check if p is a prime factor if (no % p = = 0 ): # If yes, then update no # and result while (no % p = = 0 ): no / / = p; result - = result / / p; # If no has a prime factor greater # than Math.sqrt(n) then at-most one such # prime factor exists if (no > 1 ): result - = result / / no; # Return the result return result; # Finding GCD of pairs def sumOfGCDofPairs(n): res = 0 ; for i in range ( 1 , int ( pow (n, 1 / 2 )) + 1 ): if (n % i = = 0 ): # Calculate the divisors d1 = i; d2 = n / / i; # Return count of numbers # from 1 to N with GCD d with N res + = d1 * getCount(d1, n); # Check if d1 and d2 are # equal then skip this if (d1 ! = d2): res + = d2 * getCount(d2, n); return res; # Driver code if __name__ = = '__main__' : n = 12 ; print (sumOfGCDofPairs(n)); # This code is contributed by Amit Katiyar |
C#
// C# program to find the sum // of GCD of all integers up to N // with N itself using System; class GFG{ // Function to find sum of // GCD of each numbers static int getCount( int d, int n) { int no = n / d; int result = no; // Consider all prime factors // of no. and subtract their // multiples from result for ( int p = 2; p * p <= no; ++p) { // Check if p is a prime factor if (no % p == 0) { // If yes, then update no // and result while (no % p == 0) no /= p; result -= result / p; } } // If no has a prime factor greater // than Math.Sqrt(n) then at-most // one such prime factor exists if (no > 1) result -= result / no; // Return the result return result; } // Finding GCD of pairs static int sumOfGCDofPairs( int n) { int res = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { // Calculate the divisors int d1 = i; int d2 = n / i; // Return count of numbers // from 1 to N with GCD d with N res += d1 * getCount(d1, n); // Check if d1 and d2 are // equal then skip this if (d1 != d2) res += d2 * getCount(d2, n); } } return res; } // Driver code public static void Main(String[] args) { int n = 12; Console.Write(sumOfGCDofPairs(n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript Program to find the Sum // of GCD of all integers up to N // with N itself // Function to Find Sum of // GCD of each numbers function getCount(d, n) { let no = Math.floor(n / d); let result = no; // Consider all prime factors // of no. and subtract their // multiples from result for (let p = 2; p * p <= no; ++p) { // Check if p is a prime factor if (no % p == 0) { // If yes, then update no // and result while (no % p == 0) no = Math.floor(no / p); result = Math.floor(result - result / p); } } // If no has a prime factor greater // than sqrt(n) then at-most one such // prime factor exists if (no > 1) result = Math.floor(result - result / no); // Return the result return result; } // Finding GCD of pairs function sumOfGCDofPairs(n) { let res = 0; for (let i = 1; i * i <= n; i++) { if (n % i == 0) { // Calculate the divisors let d1 = i; let d2 = Math.floor(n / i); // Return count of numbers // from 1 to N with GCD d with N res += d1 * getCount(d1, n); // Check if d1 and d2 are // equal then skip this if (d1 != d2) res += d2 * getCount(d2, n); } } return res; } // Driver code let n = 12; document.write(sumOfGCDofPairs(n)); // This code is contributed by Surbhi Tyagi. </script> |
40
Time Complexity: O(N)
Auxiliary Space: O(1)