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

Dado un entero N , la tarea es encontrar el MCD máximo posible de un par de enteros tal que su suma sea N .

Ejemplos:

Entrada: N = 30 
Salida: 15 
Explicación: GCD de (15, 15) es 15, que es el máximo GCD posible

Entrada: N = 33 
Salida: 11 
Explicación: GCD de (11, 22) es 11, que es el máximo GCD posible

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es calcular el GCD para todos los pares de enteros con suma N y encontrar el máximo GCD posible entre ellos. 
Complejidad temporal: O(N ² logN) 
Espacio auxiliar: O(1)

Enfoque eficiente: 
siga los pasos que se indican a continuación para optimizar el enfoque anterior:

• Iterar hasta √N y encontrar el mayor factor propio de N .
• Si N es primo, es decir, no se puede obtener ningún factor, imprima 1 , ya que todos los pares son coprimos.
• De lo contrario, escriba el factor más grande posible como respuesta.

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

// C++ Program to find the maximum
// possible GCD of any pair with
// sum N
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required
// GCD value
int maxGCD(int N)
{
    for (int i = 2; i * i <= N; i++) {
 
        // If i is a factor of N
        if (N % i == 0) {
 
            // Return the largest
            // factor possible
            return N / i;
        }
    }
 
    // If N is a prime number
    return 1;
}
 
// Driver Code
int main()
{
    int N = 33;
    cout << "Maximum Possible GCD value is : "
        << maxGCD(N) << endl;
    return 0;
}

// Java program to find the maximum
// possible GCD of any pair with
// sum N
class GFG{
 
// Function to find the required
// GCD value
static int maxGCD(int N)
{
    for(int i = 2; i * i <= N; i++)
    {
 
        // If i is a factor of N
        if (N % i == 0)
        {
 
            // Return the largest
            // factor possible
            return N / i;
        }
    }
 
    // If N is a prime number
    return 1;
}
     
// Driver Code
public static void main(String[] args)
{
    int N = 33;
    System.out.println("Maximum Possible GCD " +
                       "value is : " + maxGCD(N));
}
}
 
// This code is conhtributed by rutvik_56

# Python3 program to find the maximum
# possible GCD of any pair with
# sum N
 
# Function to find the required
# GCD value
def maxGCD(N):
     
    i = 2
    while(i * i <= N):
 
        # If i is a factor of N
        if (N % i == 0):
 
            # Return the largest
            # factor possible
            return N // i
         
        i += 1
 
    # If N is a prime number
    return 1
 
# Driver Code
N = 33
 
print("Maximum Possible GCD value is : ",
       maxGCD(N))
 
# This code is contributed by code_hunt

// C# program to find the maximum
// possible GCD of any pair with
// sum N
using System;
 
class GFG{
 
// Function to find the required
// GCD value
static int maxGCD(int N)
{
    for(int i = 2; i * i <= N; i++)
    {
 
        // If i is a factor of N
        if (N % i == 0)
        {
 
            // Return the largest
            // factor possible
            return N / i;
        }
    }
 
    // If N is a prime number
    return 1;
}
     
// Driver Code
public static void Main(String[] args)
{
    int N = 33;
    Console.WriteLine("Maximum Possible GCD " +
                      "value is : " + maxGCD(N));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program to find the maximum
// possible GCD of any pair with
// sum N
 
// Function to find the required
// GCD value
function maxGCD(N)
{
    for(var i = 2; i * i <= N; i++)
    {
         
        // If i is a factor of N
        if (N % i == 0)
        {
             
            // Return the largest
            // factor possible
            return N / i;
        }
    }
 
    // If N is a prime number
    return 1;
}
 
// Driver code
var N = 33;
document.write("Maximum Possible GCD " +
               "value is :" + maxGCD(N));
 
// This code is contributed by Ankita saini.
    
</script>

Maximum Possible GCD value is : 11

Complejidad de Tiempo: O(√N) 
Espacio Auxiliar: O(1)