Sum of all numbers up to N that are co-prime with N

0 0 4 minutes read

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>

Output:

Time Complexity: O(N*log₂(N)), as here we iterate loop from i=1 to N and for every i we calculate gcd(i,N) which takes log₂(N) time so overall time complexity will be O(N*log₂(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 log₂(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 zambiatek!