Suma de todos los números hasta N que son coprimos con N

Dado un número entero N , la tarea es encontrar la suma de todos los números en el rango [1, N] que son coprimos con el número dado N .

Ejemplos:

Entrada: N = 5
Salida: 10
Explicación:
Los números que son coprimos con 5 son {1, 2, 3, 4}.
Por lo tanto, la suma viene dada por 1 + 2 + 3 + 4 = 10.

Entrada: N = 6
Salida: 5
Explicación:
Los números que son coprimos con 6 son {1, 5}.
Por lo tanto, la suma requerida es igual a 1 + 5 = 6

Enfoque: la idea es iterar sobre el rango [1, N] y, para cada número, verificar si su GCD con N es igual a 1 o no. Si se determina que es cierto, para cualquier número, incluya ese número en la suma resultante. Siga los pasos a continuación para resolver el problema:

• Inicializar la suma como 0.
• Iterar sobre el rango [1, N] y si GCD de i y N es 1 , agregue i a sum .
• Después de completar los pasos anteriores, imprima el valor de la suma obtenida.

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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# 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

<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

Complejidad temporal: O(N)
Espacio auxiliar: O(1)