Encuentre M tal que MCD de M y el número dado N sea máximo

Dado un entero N mayor que 2, la tarea es encontrar un elemento M tal que MCD(N, M) sea máximo.

Ejemplos:

Entrada: N = 10
Salida: 5
Explicación:
mcd(1, 10), mcd(3, 10), mcd(7, 10), mcd(9, 10) es 1, 
 mcd(2, 10), mcd(4 , 10), mcd(6, 10), mcd(8, 10) es 2, 
 mcd(5, 10) es 5, que es el máximo.

Entrada: N = 21
Salida: 7
Explicación:
mcd(7, 21) es el máximo entre todos los enteros del 1 al 21.

Enfoque ingenuo: el enfoque más simple es recorrer todos los números en el rango [1, N-1] y encontrar el MCD de cada número con N . El número que da el MCD máximo con N es el resultado requerido.

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

Enfoque eficiente: para optimizar el enfoque anterior, observamos que el MCD de dos números será definitivamente uno de sus divisores en el rango [1, N-1] . Y, MCD será máximo si el divisor es máximo.
Por lo tanto, la idea es encontrar todos los divisores de N y almacenar un máximo de esos divisores, que es el resultado requerido.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the integer M
// such that gcd(N, M) is maximum
int findMaximumGcd(int n)
{
    // Initialize a variable
    int max_gcd = 1;
 
    // Find all the divisors of N and
    // return the maximum divisor
    for (int i = 1; i * i <= n; i++) {
 
        // Check if i is divisible by N
        if (n % i == 0) {
 
            // Update max_gcd
            if (i > max_gcd)
                max_gcd = i;
 
            if ((n / i != i)
                && (n / i != n)
                && ((n / i) > max_gcd))
                max_gcd = n / i;
        }
    }
 
    // Return the maximum value
    return max_gcd;
}
 
// Driver Code
int main()
{
    // Given Number
    int N = 10;
 
    // Function Call
    cout << findMaximumGcd(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the integer M
// such that gcd(N, M) is maximum
static int findMaximumGcd(int n)
{
     
    // Initialize a variable
    int max_gcd = 1;
 
    // Find all the divisors of N and
    // return the maximum divisor
    for(int i = 1; i * i <= n; i++)
    {
         
        // Check if i is divisible by N
        if (n % i == 0)
        {
             
            // Update max_gcd
            if (i > max_gcd)
                max_gcd = i;
 
            if ((n / i != i) &&
                (n / i != n) &&
               ((n / i) > max_gcd))
                max_gcd = n / i;
        }
    }
 
    // Return the maximum value
    return max_gcd;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Number
    int N = 10;
 
    // Function Call
    System.out.print(findMaximumGcd(N));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to find the integer M
# such that gcd(N, M) is maximum
def findMaximumGcd(n):
     
    # Initialize variables
    max_gcd = 1
    i = 1
     
    # Find all the divisors of N and
    # return the maximum divisor
    while (i * i <= n):
         
        # Check if i is divisible by N
        if n % i == 0:
             
            # Update max_gcd
            if (i > max_gcd):
                max_gcd = i
                 
            if ((n / i != i) and
                (n / i != n) and
               ((n / i) > max_gcd)):
                max_gcd = n / i
        i += 1
         
    # Return the maximum value
    return (int(max_gcd))
 
# Driver Code
if __name__ == '__main__':
     
    # Given number
    n = 10
     
    # Function call
    print(findMaximumGcd(n))
     
# This code is contributed by virusbuddah_

// C# program for the
// above approach
using System;
class GFG{
 
// Function to find the
// integer M such that
// gcd(N, M) is maximum
static int findMaximumGcd(int n)
{   
  // Initialize a variable
  int max_gcd = 1;
 
  // Find all the divisors of
  // N and return the maximum
  // divisor
  for(int i = 1;
          i * i <= n; i++)
  {
    // Check if i is
    // divisible by N
    if (n % i == 0)
    {
      // Update max_gcd
      if (i > max_gcd)
        max_gcd = i;
 
      if ((n / i != i) &&
          (n / i != n) &&
          ((n / i) > max_gcd))
        max_gcd = n / i;
    }
  }
 
  // Return the maximum
  // value
  return max_gcd;
}
 
// Driver Code
public static void Main(String[] args)
{   
  // Given Number
  int N = 10;
 
  // Function Call
  Console.Write(findMaximumGcd(N));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the integer M
// such that gcd(N, M) is maximum
function findMaximumGcd(n)
{
      
    // Initialize a variable
    let max_gcd = 1;
  
    // Find all the divisors of N and
    // return the maximum divisor
    for(let i = 1; i * i <= n; i++)
    {
          
        // Check if i is divisible by N
        if (n % i == 0)
        {
              
            // Update max_gcd
            if (i > max_gcd)
                max_gcd = i;
  
            if ((n / i != i) &&
                (n / i != n) &&
               ((n / i) > max_gcd))
                max_gcd = n / i;
        }
    }
  
    // Return the maximum value
    return max_gcd;
}
 
    // Driver Code
         
    // Given Number
    let N = 10;
  
    // Function Call
    document.write(findMaximumGcd(N));
 
</script>

5

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