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>usingnamespacestd;  // Function to return gcd of a and bintgcd(inta, intb){    // Base Case    if(a == 0)        returnb;      // Recursive GCD    returngcd(b % a, a);}  // Function to calculate the sum of all// numbers till N that are coprime with NintfindSum(unsigned intN){    // Stores the resultant sum    unsigned intsum = 0;      // Iterate over [1, N]    for(inti = 1; i < N; i++) {          // If gcd is 1        if(gcd(i, N) == 1) {              // Update sum            sum += i;        }    }      // Return the final sum    returnsum;}  // Driver Codeintmain(){    // Given N    intN = 5;      // Function Call    cout << findSum(N);    return0;} | 
Java
| // Java program for the above approachimportjava.util.*;classGFG{  // Function to return gcd // of a and bstaticintgcd(inta,                intb){  // Base Case  if(a == 0)    returnb;    // Recursive GCD  returngcd(b % a, a);}  // Function to calculate the // sum of all numbers till N // that are coprime with NstaticintfindSum(intN){  // Stores the resultant sum  intsum = 0;    // Iterate over [1, N]  for(inti = 1; i < N; i++)   {    // If gcd is 1    if(gcd(i, N) == 1)     {      // Update sum      sum += i;    }  }    // Return the final sum  returnsum;}  // Driver Codepublicstaticvoidmain(String[] args){  // Given N  intN = 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 bdefgcd(a, b):    # Base Case    if(a ==0):        returnb;      # Recursive GCD    returngcd(b %a, a);  # Function to calculate the# sum of all numbers till N# that are coprime with NdeffindSum(N):    # Stores the resultant sum    sum=0;      # Iterate over [1, N]    fori inrange(1, N):        # If gcd is 1        if(gcd(i, N) ==1):            # Update sum            sum+=i;      # Return the final sum    returnsum;  # Driver Codeif__name__ =='__main__':    # Given N    N =5;      # Function Call    print(findSum(N));  # This code is contributed by Rajput-Ji | 
C#
| // C# program for the above approachusingSystem;classGFG{  // Function to return gcd // of a and bstaticintgcd(inta,                intb){  // Base Case  if(a == 0)    returnb;    // Recursive GCD  returngcd(b % a, a);}  // Function to calculate the // sum of all numbers till N // that are coprime with NstaticintfindSum(intN){  // Stores the resultant sum  intsum = 0;    // Iterate over [1, N]  for(inti = 1; i < N; i++)   {    // If gcd is 1    if(gcd(i, N) == 1)     {      // Update sum      sum += i;    }  }    // Return the readonly sum  returnsum;}  // Driver CodepublicstaticvoidMain(String[] args){  // Given N  intN = 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 bfunctiongcd(a, b){    // Base Case    if(a == 0)        returnb;      // Recursive GCD    returngcd(b % a, a);}  // Function to calculate the sum of all// numbers till N that are coprime with NfunctionfindSum(N){    // Stores the resultant sum    varsum = 0;      // Iterate over [1, N]    for(vari = 1; i < N; i++) {          // If gcd is 1        if(gcd(i, N) == 1) {              // Update sum            sum += i;        }    }      // Return the final sum    returnsum;}  // Driver Code// Given NvarN = 5;  // Function Calldocument.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!


 
                                    







