Encuentra dos números con el MCM dado y la mínima diferencia posible

Dado un entero X , la tarea es encontrar dos enteros A y B tales que LCM(A, B) = X y la diferencia entre A y B sea la mínima posible.
Ejemplos: 
 

Entrada: X = 6 
Salida: 2 3 
LCM(2, 3) = 6 y (3 – 2) = 1 
que es el mínimo posible.
Entrada X = 7 
Salida: 1 7 
 

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 tiene la mínima diferencia posible.
A continuación se muestra la implementación del enfoque anterior: 
 

// 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 find and print the two numbers
void findNums(int x)
{
 
    int ans;
 
    // To find the factors
    for (int i = 1; i <= sqrt(x); i++) {
 
        // To check if i is a factor of x and
        // the minimum possible number
        // satisfying the given conditions
        if (x % i == 0 && lcm(i, x / i) == x) {
 
            ans = i;
        }
    }
    cout << ans << " " << (x / ans);
}
 
// Driver code
int main()
{
    int x = 12;
 
    findNums(x);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
    // Function to return the LCM of a and b
    static int lcm(int a, int b)
    {
        return (a / __gcd(a, b) * b);
    }
 
    static int __gcd(int a, int b)
    {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Function to find and print the two numbers
    static void findNums(int x)
    {
 
        int ans = -1;
 
        // To find the factors
        for (int i = 1; i <= Math.sqrt(x); i++)
        {
 
            // To check if i is a factor of x and
            // the minimum possible number
            // satisfying the given conditions
            if (x % i == 0 && lcm(i, x / i) == x)
            {
 
                ans = i;
            }
        }
        System.out.print(ans + " " + (x / ans));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int x = 12;
 
        findNums(x);
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
from math import gcd as __gcd, sqrt, ceil
 
# Function to return the LCM of a and b
def lcm(a, b):
    return (a // __gcd(a, b) * b)
 
# Function to find and print the two numbers
def findNums(x):
 
    ans = 0
 
    # To find the factors
    for i in range(1, ceil(sqrt(x))):
 
        # To check if i is a factor of x and
        # the minimum possible number
        # satisfying the given conditions
        if (x % i == 0 and lcm(i, x // i) == x):
 
            ans = i
 
    print(ans, (x//ans))
 
# Driver code
x = 12
 
findNums(x)
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the LCM of a and b
    static int lcm(int a, int b)
    {
        return (a / __gcd(a, b) * b);
    }
 
    static int __gcd(int a, int b)
    {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Function to find and print the two numbers
    static void findNums(int x)
    {
 
        int ans = -1;
 
        // To find the factors
        for (int i = 1; i <= Math.Sqrt(x); i++)
        {
 
            // To check if i is a factor of x and
            // the minimum possible number
            // satisfying the given conditions
            if (x % i == 0 && lcm(i, x / i) == x)
            {
 
                ans = i;
            }
        }
        Console.Write(ans + " " + (x / ans));
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int x = 12;
 
        findNums(x);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the approach
 
// Function to return the LCM of a and b
function lcm(a,b)
{
     return (a / __gcd(a, b) * b);
}
 
function __gcd(a,b)
{
     return b == 0 ? a : __gcd(b, a % b);
}
 
// Function to find and print the two numbers
function findNums(x)
{
    let ans = -1;
   
        // To find the factors
        for (let i = 1; i <= Math.sqrt(x); i++)
        {
   
            // To check if i is a factor of x and
            // the minimum possible number
            // satisfying the given conditions
            if (x % i == 0 && lcm(i, Math.floor(x / i)) == x)
            {
   
                ans = i;
            }
        }
        document.write(ans + " " + Math.floor(x / ans));
}
 
// Driver code
let x = 12;
findNums(x);
 
// This code is contributed by patel2127
</script>

3 4

Complejidad de tiempo: O(n ^1/2 * log(max(a, b)))

Espacio auxiliar: O(log(max(a, b)))