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

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

Ejemplos:

Entrada: N = 5
Salida: 24
Explicación:
Los números que son coprimos con 5 son {1, 2, 3, 4}.
Por lo tanto, el producto viene dado por 1 * 2 * 3 * 4 = 24.

Entrada: N = 6
Salida: 5
Explicación:
Los números que son coprimos con 6 son {1, 5}.
Por lo tanto, el producto requerido es igual a 1 * 5 = 5

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 encuentra que es cierto para cualquier número, entonces incluya ese número en el producto resultante. 
Siga los pasos a continuación para resolver el problema:

1. Inicialice el producto como 1 .
2. Iterar sobre el rango [1, N] y si GCD de i y N es 1 , multiplicar el producto con i .
3. Después del paso anterior, imprima el valor del producto .

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 find the product of
// all the numbers till N that are
// relatively prime to N
int findProduct(unsigned int N)
{
    // Stores the resultant product
    unsigned int result = 1;
 
    // Iterate over [2, N]
    for (int i = 2; i < N; i++) {
 
        // If gcd is 1, then find the
        // product with result
        if (gcd(i, N) == 1) {
            result *= i;
        }
 
        
    }
   // Return the final product
        return result;
}
 
// Driver Code
int main()
{
    int N = 5;
 
    cout << findProduct(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 find the
// product of all the
// numbers till N that are
// relatively prime to N
static int findProduct(int N)
{
  // Stores the resultant
  // product
  int result = 1;
 
  // Iterate over [2, N]
  for (int i = 2; i < N; i++)
  {
    // If gcd is 1, then
    // find the product
    // with result
    if (gcd(i, N) == 1)
    {
      result *= i;
    }
  }
   
  // Return the final
  // product
  return result;
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 5;
  System.out.print(findProduct(N));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 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 find the
# product of all the
# numbers till N that are
# relatively prime to N
def findProduct(N):
   
    # Stores the resultant
    # product
    result = 1;
 
    # Iterate over [2, N]
    for i in range(2, N):
       
        # If gcd is 1, then
        # find the product
        # with result
        if (gcd(i, N) == 1):
            result *= i;
 
    # Return the final
    # product
    return result;
 
# Driver Code
if __name__ == '__main__':
   
    N = 5;
    print(findProduct(N));
 
# This code is contributed by 29AjayKumar

// 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 find the
// product of all the
// numbers till N that are
// relatively prime to N
static int findProduct(int N)
{
   
  // Stores the resultant
  // product
  int result = 1;
 
  // Iterate over [2, N]
  for(int i = 2; i < N; i++)
  {
     
    // If gcd is 1, then
    // find the product
    // with result
    if (gcd(i, N) == 1)
    {
      result *= i;
    }
  }
   
  // Return the readonly
  // product
  return result;
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 5;
   
  Console.Write(findProduct(N));
}
}
 
// This code is contributed by Amit Katiyar

<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 find the product of
// all the numbers till N that are
// relatively prime to N
function findProduct( N)
{
    // Stores the resultant product
    var result = 1;
 
    // Iterate over [2, N]
    for (var i = 2; i < N; i++) {
 
        // If gcd is 1, then find the
        // product with result
        if (gcd(i, N) == 1) {
            result *= i;
        }
        
    }
   // Return the final product
        return result;
}
 
// Driver Code
var N = 5;
document.write(findProduct(N))
 
</script>

24

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