Máximo MCD posible para un par de enteros con producto N

Dado un entero N , la tarea es encontrar el MCD máximo posible entre todos los pares de enteros con producto N .
Ejemplos:

Entrada: N=12 
Salida: 2 
Explicación: 
Todos los pares posibles con el producto 12 son {1, 12}, {2, 6}, {3, 4} 
MCD(1, 12) = 1 
MCD(2, 6) = 2 
MCD(3, 4) = 1 
Por lo tanto, el máximo posible MCD = máximo(1, 2, 1) = 2
Entrada: 4 
Salida: 4 
Explicación: 
Todos los pares posibles con el producto 4 son {1, 4}, {2, 2 } 
MCD(1, 4) = 1 
MCD(2, 2) = 2 
Por lo tanto, máximo posible MCD = máximo(1, 2) = 2

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es generar todos los pares posibles con el producto N y calcular el GCD de todos esos pares. Finalmente, imprima el GCD máximo obtenido. 
Complejidad de tiempo: O(NlogN) 
Espacio auxiliar: O(1)
Enfoque eficiente: 
El enfoque anterior puede optimizarse encontrando todos los divisores del número dado N . Para cada par de divisores obtenidos, calcula su MCD. Finalmente, imprima el GCD máximo obtenido.
Siga los pasos a continuación para resolver el problema:

• Declare una variable maxGcd para realizar un seguimiento del GCD máximo.
• Iterar hasta √N y para cada entero, verificar si es un factor de N.
• Si N es divisible por i , calcule el MCD del par de factores (i, N / i) .
• Compare con GCD(i, N / i) y actualice maxGcd .
• Finalmente, imprima maxGcd .

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
/// the maximum GCD
int getMaxGcd(int N)
{
    int maxGcd = INT_MIN, A, B;
 
    // To find all divisors of N
    for (int i = 1; i <= sqrt(N); i++) {
 
        // If i is a factor
        if (N % i == 0) {
            // Store the pair of factors
            A = i, B = N / i;
 
            // Store the maximum GCD
            maxGcd = max(maxGcd, __gcd(A, B));
        }
    }
 
    // Return the maximum GCD
    return maxGcd;
}
 
// Driver Code
int main()
{
 
    int N = 18;
    cout << getMaxGcd(N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
     
// Function to return
// the maximum GCD
static int getMaxGcd(int N)
{
    int maxGcd = Integer.MIN_VALUE, A, B;
     
    // To find all divisors of N
    for(int i = 1; i <= Math.sqrt(N); i++)
    {
         
        // If i is a factor
        if (N % i == 0)
        {
             
            // Store the pair of factors
            A = i;
            B = N / i;
         
            // Store the maximum GCD
            maxGcd = Math.max(maxGcd, gcd(A, B));
        }
    }
     
    // Return the maximum GCD
    return maxGcd;
}
     
// Driver Code
public static void main(String s[])
{
    int N = 18;
     
    System.out.println(getMaxGcd(N));
}
}
 
// This code is contributed by rutvik_56

# Python3 program to implement
# the above approach
import sys
import math
 
# Function to return
# the maximum GCD
def getMaxGcd(N):
     
    maxGcd = -sys.maxsize - 1
 
    # To find all divisors of N
    for i in range(1, int(math.sqrt(N)) + 1):
 
        # If i is a factor
        if (N % i == 0):
             
            # Store the pair of factors
            A = i
            B = N // i
 
            # Store the maximum GCD
            maxGcd = max(maxGcd, math.gcd(A, B))
         
    # Return the maximum GCD
    return maxGcd
 
# Driver Code
N = 18
 
print(getMaxGcd(N))
 
# This code is contributed by code_hunt

// C# program to implement
// the above approach
using System;
class GFG{
     
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
     
// Function to return
// the maximum GCD
static int getMaxGcd(int N)
{
    int maxGcd = int.MinValue, A, B;
     
    // To find all divisors of N
    for(int i = 1; i <= Math.Sqrt(N); i++)
    {
         
        // If i is a factor
        if (N % i == 0)
        {
             
            // Store the pair of factors
            A = i;
            B = N / i;
         
            // Store the maximum GCD
            maxGcd = Math.Max(maxGcd, gcd(A, B));
        }
    }
     
    // Return the maximum GCD
    return maxGcd;
}
     
// Driver Code
public static void Main(String []s)
{
    int N = 18;
     
    Console.WriteLine(getMaxGcd(N));
}
}
 
// This code is contributed by sapnasingh4991

<script>
// javascript program to implement
// the above approach
 
    function gcd(a , b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Function to return
    // the maximum GCD
    function getMaxGcd(N)
    {
        var maxGcd = Number.MIN_VALUE, A, B;
 
        // To find all divisors of N
        for (i = 1; i <= Math.sqrt(N); i++)
        {
 
            // If i is a factor
            if (N % i == 0)
            {
 
                // Store the pair of factors
                A = i;
                B = N / i;
 
                // Store the maximum GCD
                maxGcd = Math.max(maxGcd, gcd(A, B));
            }
        }
 
        // Return the maximum GCD
        return maxGcd;
    }
 
    // Driver Code
        var N = 18;
        document.write(getMaxGcd(N));
 
// This code is contributed by aashish1995
</script>

3

Complejidad de tiempo: O(√N*log(N)) 
Espacio auxiliar: O(1)