Encuentre HCF de dos números sin usar recursividad o algoritmo euclidiano

Dados dos enteros x e y , la tarea es encontrar el HCF de los números sin usar la recursividad o el método euclidiano.

Ejemplos: 

Entrada: x = 16, y = 32 
Salida: 16

Entrada: x = 12, y = 15 
Salida: 3 
 

Enfoque: HCF de dos números es el número más grande que puede dividir a ambos números. Si el menor de los dos números puede dividir al número mayor, entonces el HCF es el número menor. De lo contrario, a partir de (menor / 2) a 1, verifique si el elemento actual divide ambos números. En caso afirmativo, entonces es el HCF requerido.

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

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the HCF of x and y
int getHCF(int x, int y)
{
 
    // Minimum of the two numbers
    int minimum = min(x, y);
 
    // If both the numbers are divisible
    // by the minimum of these two then
    // the HCF is equal to the minimum
    if (x % minimum == 0 && y % minimum == 0)
        return minimum;
 
    // Highest number between 2 and minimum/2
    // which can divide both the numbers
    // is the required HCF
    for (int i = minimum / 2; i >= 2; i--) {
 
        // If both the numbers
        // are divisible by i
        if (x % i == 0 && y % i == 0)
            return i;
    }
 
    // 1 divides every number
    return 1;
}
 
// Driver code
int main()
{
    int x = 16, y = 32;
    cout << getHCF(x, y);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the HCF of x and y
static int getHCF(int x, int y)
{
 
    // Minimum of the two numbers
    int minimum = Math.min(x, y);
 
    // If both the numbers are divisible
    // by the minimum of these two then
    // the HCF is equal to the minimum
    if (x % minimum == 0 && y % minimum == 0)
        return minimum;
 
    // Highest number between 2 and minimum/2
    // which can divide both the numbers
    // is the required HCF
    for (int i = minimum / 2; i >= 2; i--)
    {
 
        // If both the numbers
        // are divisible by i
        if (x % i == 0 && y % i == 0)
            return i;
    }
 
    // 1 divides every number
    return 1;
}
 
// Driver code
public static void main(String[] args)
{
    int x = 16, y = 32;
    System.out.println(getHCF(x, y));
}
}
 
// This code is contributed by Code_Mech.

# Python3 implementation of the approach
 
# Function to return the HCF of x and y
def getHCF(x, y):
 
    # Minimum of the two numbers
    minimum = min(x, y)
 
    # If both the numbers are divisible
    # by the minimum of these two then
    # the HCF is equal to the minimum
    if (x % minimum == 0 and y % minimum == 0):
        return minimum
 
    # Highest number between 2 and minimum/2
    # which can divide both the numbers
    # is the required HCF
    for i in range(minimum // 2, 1, -1):
         
        # If both the numbers are divisible by i
        if (x % i == 0 and y % i == 0):
            return i
 
    # 1 divides every number
    return 1
 
# Driver code
x, y = 16, 32
print(getHCF(x, y))
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the HCF of x and y
static int getHCF(int x, int y)
{
 
    // Minimum of the two numbers
    int minimum = Math.Min(x, y);
 
    // If both the numbers are divisible
    // by the minimum of these two then
    // the HCF is equal to the minimum
    if (x % minimum == 0 && y % minimum == 0)
        return minimum;
 
    // Highest number between 2 and minimum/2
    // which can divide both the numbers
    // is the required HCF
    for (int i = minimum / 2; i >= 2; i--)
    {
 
        // If both the numbers
        // are divisible by i
        if (x % i == 0 && y % i == 0)
            return i;
    }
 
    // 1 divides every number
    return 1;
}
 
// Driver code
static void Main()
{
    int x = 16, y = 32;
    Console.WriteLine(getHCF(x, y));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function to return the HCF of x and y
function getHCF($x, $y)
{
 
    // Minimum of the two numbers
    $minimum = min($x, $y);
 
    // If both the numbers are divisible
    // by the minimum of these two then
    // the HCF is equal to the minimum
    if ($x % $minimum == 0 &&
        $y % $minimum == 0)
        return $minimum;
 
    // Highest number between 2 and minimum/2
    // which can divide both the numbers
    // is the required HCF
    for ($i = $minimum / 2; $i >= 2; $i--)
    {
 
        // If both the numbers
        // are divisible by i
        if ($x % $i == 0 &&
            $y % $i == 0)
            return $i;
    }
 
    // 1 divides every number
    return 1;
}
 
// Driver code
$x = 16; $y = 32;
echo(getHCF($x, $y));
 
// This code is contributed
// by Code_Mech.
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the HCF of x and y
function getHCF(x, y)
{
     
    // Minimum of the two numbers
    var minimum = Math.min(x, y);
 
    // If both the numbers are divisible
    // by the minimum of these two then
    // the HCF is equal to the minimum
    if (x % minimum == 0 && y % minimum == 0)
        return minimum;
 
    // Highest number between 2 and minimum/2
    // which can divide both the numbers
    // is the required HCF
    for(var i = minimum / 2; i >= 2; i--)
    {
         
        // If both the numbers
        // are divisible by i
        if (x % i == 0 && y % i == 0)
            return i;
    }
 
    // 1 divides every number
    return 1;
}
 
// Driver code
var x = 16, y = 32;
 
document.write(getHCF(x, y));
 
// This code is contributed by noob2000
 
</script>

16

Complejidad de tiempo: O(min(x, y)), aquí x e y son dos parámetros de entrada.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.