Valor mínimo posible de max(A, B) tal que LCM(A, B) = C

Dado un entero C , la tarea es encontrar el valor mínimo posible de max(A, B) tal que LCM(A, B) = C .
Ejemplos: 
 

Entrada: C = 6 
Salida:
max(1, 6) = 6 
max(2, 3) = 3 
y min(6, 3) = 3
Entrada: C = 9 
Salida:
 

Enfoque: un enfoque para resolver este problema es encontrar todos los factores del número dado usando el enfoque discutido en este artículo y luego encontrar el par (A, B) que satisface las condiciones dadas y tomar el mínimo general del máximo de estos . pares
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the LCM of a and b
int lcm(int a, int b)
{
    return (a / __gcd(a, b) * b);
}
 
// Function to return the minimized value
int getMinValue(int c)
{
    int ans = INT_MAX;
 
    // To find the factors
    for (int i = 1; i <= sqrt(c); i++) {
 
        // To check if i is a factor of c and
        // the minimum possible number
        // satisfying the given conditions
        if (c % i == 0 && lcm(i, c / i) == c) {
 
            // Update the answer
            ans = min(ans, max(i, c / i));
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int c = 6;
 
    cout << getMinValue(c);
 
    return 0;
}

Java

// Java implementation of the approach
class Solution
{
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
        return b;
        if (b == 0)
        return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
     
    // Function to return the LCM of a and b
    static int lcm(int a, int b)
    {
        return (a / __gcd(a, b) * b);
    }
 
    // Function to return the minimized value
    static int getMinValue(int c)
    {
        int ans = Integer.MAX_VALUE;
 
        // To find the factors
        for (int i = 1; i <= Math.sqrt(c); i++)
        {
 
            // To check if i is a factor of c and
            // the minimum possible number
            // satisfying the given conditions
            if (c % i == 0 && lcm(i, c / i) == c)
            {
 
                // Update the answer
                ans = Math.min(ans, Math.max(i, c / i));
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int c = 6;
 
        System.out.println(getMinValue(c));
    }
}
 
// This code is contributed by Arnab Kundu

Python3

# Python implementation of the approach
import sys
 
# Recursive function to return gcd of a and b
def __gcd(a, b):
     
    # Everything divides 0
    if (a == 0):
        return b;
    if (b == 0):
        return a;
 
    # base case
    if (a == b):
        return a;
 
    # a is greater
    if (a > b):
        return __gcd(a - b, b);
    return __gcd(a, b - a);
 
# Function to return the LCM of a and b
def lcm(a, b):
    return (a / __gcd(a, b) * b);
 
# Function to return the minimized value
def getMinValue(c):
    ans = sys.maxsize;
 
    # To find the factors
    for i in range(1, int(pow(c, 1/2)) + 1):
 
        # To check if i is a factor of c and
        # the minimum possible number
        # satisfying the given conditions
        if (c % i == 0 and lcm(i, c / i) == c):
 
            # Update the answer
            ans = min(ans, max(i, c / i));
    return int(ans);
 
# Driver code
if __name__ == '__main__':
    c = 6;
 
    print(getMinValue(c));
     
# This code is contributed by 29AjayKumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
        return b;
        if (b == 0)
        return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
     
    // Function to return the LCM of a and b
    static int lcm(int a, int b)
    {
        return (a / __gcd(a, b) * b);
    }
 
    // Function to return the minimized value
    static int getMinValue(int c)
    {
        int ans = int.MaxValue;
 
        // To find the factors
        for (int i = 1; i <= Math.Sqrt(c); i++)
        {
 
            // To check if i is a factor of c and
            // the minimum possible number
            // satisfying the given conditions
            if (c % i == 0 && lcm(i, c / i) == c)
            {
 
                // Update the answer
                ans = Math.Min(ans, Math.Max(i, c / i));
            }
        }
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int c = 6;
 
        Console.WriteLine(getMinValue(c));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// javascript implementation of the approach
 
// Recursive function to return gcd of a and b
function __gcd(a , b)
{
    // Everything divides 0
    if (a == 0)
    return b;
    if (b == 0)
    return a;
     
    // base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
    return __gcd(a, b - a);
}
 
// Function to return the LCM of a and b
function lcm(a , b)
{
    return (a / __gcd(a, b) * b);
}
 
// Function to return the minimized value
function getMinValue(c)
{
    var ans = Number.MAX_VALUE;
 
    // To find the factors
    for (i = 1; i <= Math.sqrt(c); i++)
    {
 
        // To check if i is a factor of c and
        // the minimum possible number
        // satisfying the given conditions
        if (c % i == 0 && lcm(i, c / i) == c)
        {
 
            // Update the answer
            ans = Math.min(ans, Math.max(i, c / i));
        }
    }
    return ans;
}
 
// Driver code
 
var c = 6;
 
document.write(getMinValue(c));
 
// This code contributed by shikhasingrajput
 
</script>
Producción: 

3

 

Publicación traducida automáticamente

Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *