Given an integer N, the task is to find the sum of all numbers in the range [1, N] that are co-prime with the given number N.
Examples:
Input: N = 5
Output: 10
Explanation:
Numbers which are co-prime with 5 are {1, 2, 3, 4}.
Therefore, the sum is given by 1 + 2 + 3 + 4 = 10.Input: N = 6
Output: 5
Explanation:
Numbers which are co-prime to 6 are {1, 5}.
Therefore, the required sum is equal to 1 + 5 = 6
Approach: The idea is to iterate over the range [1, N], and for every number, check if its GCD with N is equal to 1 or not. If found to be true, for any number, then include that number in the resultant sum. Follow the steps below to solve the problem:
- Initialize the sum as 0.
- Iterate over the range [1, N] and if GCD of i and N is 1, add i to sum.
- After completing the above steps, print the value of the sum obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach Â
#include <iostream> using namespace std; Â
// Function to return gcd of a and b int gcd( int a, int b) {     // Base Case     if (a == 0)         return b; Â
    // Recursive GCD     return gcd(b % a, a); } Â
// Function to calculate the sum of all // numbers till N that are coprime with N int findSum(unsigned int N) {     // Stores the resultant sum     unsigned int sum = 0; Â
    // Iterate over [1, N]     for ( int i = 1; i < N; i++) { Â
        // If gcd is 1         if (gcd(i, N) == 1) { Â
            // Update sum             sum += i;         }     } Â
    // Return the final sum     return sum; } Â
// Driver Code int main() { Â Â Â Â // Given N Â Â Â Â int N = 5; Â
    // Function Call     cout << findSum(N);     return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ Â
// Function to return gcd // of a and b static int gcd( int a,                int b) {   // Base Case   if (a == 0 )     return b; Â
  // Recursive GCD   return gcd(b % a, a); } Â
// Function to calculate the // sum of all numbers till N // that are coprime with N static int findSum( int N) {   // Stores the resultant sum   int sum = 0 ; Â
  // Iterate over [1, N]   for ( int i = 1 ; i < N; i++)   {     // If gcd is 1     if (gcd(i, N) == 1 )     {       // Update sum       sum += i;     }   } Â
  // Return the final sum   return sum; } Â
// Driver Code public static void main(String[] args) { Â Â // Given N Â Â int N = 5 ; Â
  // Function Call   System.out.print(findSum(N)); } } Â
// This code is contributed by gauravrajput1 |
Python3
# Python program for # the above approach Â
# Function to return gcd # of a and b def gcd(a, b):     # Base Case     if (a = = 0 ):         return b; Â
    # Recursive GCD     return gcd(b % a, a); Â
# Function to calculate the # sum of all numbers till N # that are coprime with N def findSum(N):     # Stores the resultant sum     sum = 0 ; Â
    # Iterate over [1, N]     for i in range ( 1 , N):         # If gcd is 1         if (gcd(i, N) = = 1 ):             # Update sum             sum + = i; Â
    # Return the final sum     return sum ; Â
# Driver Code if __name__ = = '__main__' : Â Â Â Â # Given N Â Â Â Â N = 5 ; Â
    # Function Call     print (findSum(N)); Â
# This code is contributed by Rajput-Ji |
C#
// C# program for the above approach using System; class GFG{ Â
// Function to return gcd // of a and b static int gcd( int a,                int b) {   // Base Case   if (a == 0)     return b; Â
  // Recursive GCD   return gcd(b % a, a); } Â
// Function to calculate the // sum of all numbers till N // that are coprime with N static int findSum( int N) {   // Stores the resultant sum   int sum = 0; Â
  // Iterate over [1, N]   for ( int i = 1; i < N; i++)   {     // If gcd is 1     if (gcd(i, N) == 1)     {       // Update sum       sum += i;     }   } Â
  // Return the readonly sum   return sum; } Â
// Driver Code public static void Main(String[] args) { Â Â // Given N Â Â int N = 5; Â
  // Function Call   Console.Write(findSum(N)); } } Â
// This code is contributed by shikhasingrajput |
Javascript
<script> Â
// Javascript program for the above approach Â
// Function to return gcd of a and b function gcd(a, b) {     // Base Case     if (a == 0)         return b; Â
    // Recursive GCD     return gcd(b % a, a); } Â
// Function to calculate the sum of all // numbers till N that are coprime with N function findSum(N) {     // Stores the resultant sum     var sum = 0; Â
    // Iterate over [1, N]     for ( var i = 1; i < N; i++) { Â
        // If gcd is 1         if (gcd(i, N) == 1) { Â
            // Update sum             sum += i;         }     } Â
    // Return the final sum     return sum; } Â
// Driver Code // Given N var N = 5; Â
// Function Call document.write(findSum(N)); Â
Â
</script> |
10
Â
Time Complexity: O(N*log2(N)), as here we iterate loop from i=1 to N and for every i we calculate gcd(i,N) which takes log2(N) time so overall time complexity will be O(N*log2(N)) (for doing gcd of two number a&b we need time log2(max(a,b)), here among i and N, N is the maximum number so log2(N) for gcd)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!