MCD máximo entre todos los pares (i, j) de los primeros N números naturales

Dado un entero positivo N > 1 , la tarea es encontrar el MCD máximo entre todos los pares (i, j) tal que i < j < N .
Ejemplos:

Entrada: N = 3
Salida: 3
Explicación:
Todos los pares posibles son: (1, 2) (1, 3) (2, 3) con GCD 1.
Entrada: N = 4
Salida: 2
Explicación:
De todos los posibles empareja el par con max GCD es (2, 4) con un valor de 2.

Enfoque ingenuo: genere todos los pares posibles de enteros del rango [1, N] y calcule el GCD de todos los pares. Finalmente, imprima el GCD máximo obtenido.

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 maximum gcd
// of all pairs possible from
// first n natural numbers
int maxGCD(int n)
{
    // Stores maximum gcd
    int maxHcf = INT_MIN;
 
    // Iterate over all possible pairs
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
 
            // Update maximum GCD
            maxHcf
                = max(maxHcf, __gcd(i, j));
        }
    }
 
    return maxHcf;
}
 
// Driver Code
int main()
{
    int n = 4;
    cout << maxGCD(n);
 
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find maximum gcd
// of all pairs possible from
// first n natural numbers
static int maxGCD(int n)
{
  // Stores maximum gcd
  int maxHcf = Integer.MIN_VALUE;
 
  // Iterate over all possible pairs
  for (int i = 1; i <= n; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      // Update maximum GCD
      maxHcf = Math.max(maxHcf,
                        __gcd(i, j));
    }
  }
 
  return maxHcf;
}
   
static int __gcd(int a, int b) 
{ 
  return b == 0 ? a :
         __gcd(b, a % b);    
}
   
// Driver Code
public static void main(String[] args)
{
  int n = 4;
  System.out.print(maxGCD(n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for
# the above approach
def __gcd(a, b):
    if(b == 0):
        return a;
    else:
        return __gcd(b, a % b);
 
# Function to find maximum gcd
# of all pairs possible from
# first n natural numbers
def maxGCD(n):
   
    # Stores maximum gcd
    maxHcf = -2391734235435;
 
    # Iterate over all possible pairs
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
           
            # Update maximum GCD
            maxHcf = max(maxHcf, __gcd(i, j));
    return maxHcf;
 
# Driver Code
if __name__ == '__main__':
    n = 4;
    print(maxGCD(n));
 
# This code is contributed by gauravrajput1

// C# program for
// the above approach
using System;
class GFG{
 
// Function to find maximum gcd
// of all pairs possible from
// first n natural numbers
static int maxGCD(int n)
{
  // Stores maximum gcd
  int maxHcf = int.MinValue;
 
  // Iterate over all possible pairs
  for (int i = 1; i <= n; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      // Update maximum GCD
      maxHcf = Math.Max(maxHcf,
                        __gcd(i, j));
    }
  }
 
  return maxHcf;
}
   
static int __gcd(int a, int b) 
{ 
  return b == 0 ? a :
         __gcd(b, a % b);    
}
   
// Driver Code
public static void Main(String[] args)
{
  int n = 4;
  Console.Write(maxGCD(n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript program for
// the above approach
 
    // Function to find maximum gcd
    // of all pairs possible from
    // first n natural numbers
    function maxGCD(n) {
        // Stores maximum gcd
        var maxHcf = Number.MIN_VALUE;
 
        // Iterate over all possible pairs
        for (i = 1; i <= n; i++) {
            for (j = i + 1; j <= n; j++) {
                // Update maximum GCD
                maxHcf = Math.max(maxHcf, __gcd(i, j));
            }
        }
 
        return maxHcf;
    }
 
    function __gcd(a , b) {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Driver Code
     
        var n = 4;
        document.write(maxGCD(n));
 
// This code contributed by umadevi9616
</script>

2

Complejidad de tiempo: O(N ² log N) 
Espacio auxiliar: O(1)
Enfoque eficiente: El GCD de N y N / 2 es N / 2, que es el máximo de todos los GCD posibles para cualquier par de 1 a N .

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum GCD
// among all the pairs from
// first n natural numbers
int maxGCD(int n)
{
 
    // Return max GCD
    return (n / 2);
}
 
// Driver Code
int main()
{
    int n = 4;
    cout << maxGCD(n);
 
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Function to find the maximum GCD
// among all the pairs from
// first n natural numbers
static int maxGCD(int n)
{
     
    // Return max GCD
    return (n / 2);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 4;
 
    System.out.print(maxGCD(n));
}
}
 
// This code is contributed by Dewanti

# Python3 implementation of the
# above approach
 
# Function to find the maximum GCD
# among all the pairs from first n
# natural numbers
def maxGCD(n):
 
    # Return max GCD
    return (n // 2);
 
# Driver code
if __name__ == '__main__':
     
    n = 4;
 
    print(maxGCD(n));
 
# This code is contributed by Amit Katiyar

// C# implementation of
// the above approach
using System;
class GFG{
 
// Function to find the maximum GCD
// among all the pairs from
// first n natural numbers
static int maxGCD(int n)
{
  // Return max GCD
  return (n / 2);
}
 
// Driver code
public static void Main(String[] args)
{
  int n = 4;
  Console.Write(maxGCD(n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the above approach
 
// Function to find the maximum GCD
// among all the pairs from
// first n natural numbers
function maxGCD(n)
{
 
    // Return max GCD
    return parseInt(n / 2);
}
 
// Driver Code
var n = 4;
document.write( maxGCD(n));
 
// This code is contributed by rrrtnx.
</script>

2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)