Encuentre enteros distintos para un triplete con un producto dado

Dado un entero X , la tarea es encontrar los tres enteros distintos mayores que 1 , es decir , A , B y C tales que (A * B * C) = X. Si no existe tal triplete, imprima -1 .
Ejemplos: 

Entrada: X = 64 
Salida: 2 4 8 
(2 * 4 * 8) = 64
Entrada: X = 32 
Salida: -1 
No existe tal triplete. 

Enfoque: supongamos que tenemos un triplete (A, B, C) . Note que, para que su producto sea igual a X , cada uno de los enteros tiene que ser un factor de X . Por lo tanto, almacene todos los factores de X en tiempo O(sqrt(X)) usando el enfoque que se analiza en este artículo. 
Habrá como máximo factores sqrt (X) ahora. A continuación, itere en cada factor ejecutando dos bucles, uno seleccionando A y otro seleccionando B . Ahora bien, si este triplete es válido, es decir, C = X / (A * B) donde C también es un factor de X. Para verificar eso, almacene todos los factores en unconjunto_desordenado . Si se encuentra un triplete válido, imprima el triplete; de ​​lo contrario, imprima -1 .
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 find the required triplets
void findTriplets(int x)
{
    // To store the factors
    vector<int> fact;
    unordered_set<int> factors;
 
    // Find factors in sqrt(x) time
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            fact.push_back(i);
            if (x / i != i)
                fact.push_back(x / i);
            factors.insert(i);
            factors.insert(x / i);
        }
    }
 
    bool found = false;
    int k = fact.size();
    for (int i = 0; i < k; i++) {
 
        // Choose a factor
        int a = fact[i];
        for (int j = 0; j < k; j++) {
 
            // Choose another factor
            int b = fact[j];
 
            // These conditions need to be
            // met for a valid triplet
            if ((a != b) && (x % (a * b) == 0)
                && (x / (a * b) != a)
                && (x / (a * b) != b)
                && (x / (a * b) != 1)) {
 
                // Print the valid triplet
                cout << a << " " << b << " "
                     << (x / (a * b));
                found = true;
                break;
            }
        }
 
        // Triplet found
        if (found)
            break;
    }
 
    // Triplet not found
    if (!found)
        cout << "-1";
}
 
// Driver code
int main()
{
    int x = 105;
 
    findTriplets(x);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to find the required triplets
static void findTriplets(int x)
{
    // To store the factors
    Vector<Integer> fact = new Vector<Integer>();
    HashSet<Integer> factors = new HashSet<Integer>();
 
    // Find factors in Math.sqrt(x) time
    for (int i = 2; i <= Math.sqrt(x); i++)
    {
        if (x % i == 0)
        {
            fact.add(i);
            if (x / i != i)
                fact.add(x / i);
            factors.add(i);
            factors.add(x / i);
        }
    }
 
    boolean found = false;
    int k = fact.size();
    for (int i = 0; i < k; i++)
    {
 
        // Choose a factor
        int a = fact.get(i);
        for (int j = 0; j < k; j++)
        {
 
            // Choose another factor
            int b = fact.get(j);
 
            // These conditions need to be
            // met for a valid triplet
            if ((a != b) && (x % (a * b) == 0)
                && (x / (a * b) != a)
                && (x / (a * b) != b)
                && (x / (a * b) != 1))
            {
 
                // Print the valid triplet
                System.out.print(a+ " " + b + " "
                    + (x / (a * b)));
                found = true;
                break;
            }
        }
 
        // Triplet found
        if (found)
            break;
    }
 
    // Triplet not found
    if (!found)
        System.out.print("-1");
}
 
// Driver code
public static void main(String[] args)
{
    int x = 105;
 
    findTriplets(x);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
from math import sqrt
 
# Function to find the required triplets
def findTriplets(x) :
 
    # To store the factors
    fact = [];
    factors = set();
 
    # Find factors in sqrt(x) time
    for i in range(2, int(sqrt(x))) :
        if (x % i == 0) :
            fact.append(i);
             
            if (x / i != i) :
                fact.append(x // i);
                 
            factors.add(i);
            factors.add(x // i);
 
    found = False;
    k = len(fact);
     
    for i in range(k) :
 
        # Choose a factor
        a = fact[i];
         
        for j in range(k) :
 
            # Choose another factor
            b = fact[j];
 
            # These conditions need to be
            # met for a valid triplet
            if ((a != b) and (x % (a * b) == 0)
                and (x / (a * b) != a)
                and (x / (a * b) != b)
                and (x / (a * b) != 1)) :
 
                # Print the valid triplet
                print(a,b,x // (a * b));
                found = True;
                break;
     
        # Triplet found
        if (found) :
            break;
 
    # Triplet not found
    if (not found) :
        print("-1");
 
# Driver code
if __name__ == "__main__" :
 
    x = 105;
 
    findTriplets(x);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the required triplets
static void findTriplets(int x)
{
    // To store the factors
    List<int> fact = new List<int>();
    HashSet<int> factors = new HashSet<int>();
 
    // Find factors in Math.Sqrt(x) time
    for (int i = 2; i <= Math.Sqrt(x); i++)
    {
        if (x % i == 0)
        {
            fact.Add(i);
            if (x / i != i)
                fact.Add(x / i);
            factors.Add(i);
            factors.Add(x / i);
        }
    }
 
    bool found = false;
    int k = fact.Count;
    for (int i = 0; i < k; i++)
    {
 
        // Choose a factor
        int a = fact[i];
        for (int j = 0; j < k; j++)
        {
 
            // Choose another factor
            int b = fact[j];
 
            // These conditions need to be
            // met for a valid triplet
            if ((a != b) && (x % (a * b) == 0)
                && (x / (a * b) != a)
                && (x / (a * b) != b)
                && (x / (a * b) != 1))
            {
 
                // Print the valid triplet
                Console.Write(a+ " " + b + " "
                    + (x / (a * b)));
                found = true;
                break;
            }
        }
 
        // Triplet found
        if (found)
            break;
    }
 
    // Triplet not found
    if (!found)
        Console.Write("-1");
}
 
// Driver code
public static void Main(String[] args)
{
    int x = 105;
 
    findTriplets(x);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to find the required triplets
function findTriplets(x)
{
    // To store the factors
    let fact = [];
    let factors = new Set();
  
    // Find factors in Math.sqrt(x) time
    for (let i = 2; i <= Math.sqrt(x); i++)
    {
        if (x % i == 0)
        {
            fact.push(i);
            if (x / i != i)
                fact.push(x / i);
            factors.add(i);
            factors.add(x / i);
        }
    }
  
    let found = false;
    let k = fact.length;
    for (let i = 0; i < k; i++)
    {
  
        // Choose a factor
        let a = fact[i];
        for (let j = 0; j < k; j++)
        {
  
            // Choose another factor
            let b = fact[j];
  
            // These conditions need to be
            // met for a valid triplet
            if ((a != b) && (x % (a * b) == 0)
                && (x / (a * b) != a)
                && (x / (a * b) != b)
                && (x / (a * b) != 1))
            {
  
                // Print the valid triplet
                document.write(a+ " " + b + " "
                    + (x / (a * b)));
                found = true;
                break;
            }
        }
  
        // Triplet found
        if (found)
            break;
    }
  
    // Triplet not found
    if (!found)
        document.write("-1");
}
  
// Driver code
     
      let x = 105;
  
    findTriplets(x);
                                                                                             
</script>

3 5 7

Complejidad de tiempo: O(N), N=X

Espacio Auxiliar: O(N)