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 bint 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 Nint 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 Codeint main(){Â Â Â Â // Given NÂ Â Â Â int N = 5;Â
    // Function Call    cout << findSum(N);    return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{Â
// Function to return gcd // of a and bstatic 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 Nstatic 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 Codepublic 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 bdef 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 Ndef 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 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 approachusing System;class GFG{Â
// Function to return gcd // of a and bstatic 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 Nstatic 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 Codepublic 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 bfunction 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 Nfunction 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 Nvar N = 5;Â
// Function Calldocument.write(findSum(N));Â
Â
</script> |
Output:Â
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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/sum-of-all-numbers-up-to-n-that-are-co-prime-with-n/ […]