Dado un número N. Imprime tres números distintos (>=1) cuyo producto sea igual a N. imprime -1 si no es posible encontrar los tres números.
Ejemplos:
Entrada: 64
Salida: 2 4 8
Explicación:
(2*4*8 = 64)
Entrada: 24
Salida: 2 3 4
Explicación:
(2*3*4 = 24)
Entrada: 12
Salida: -1
Explicación:
No existe tal triplete existe
Acercarse:
- Cree una array que almacene todos los divisores del número dado usando el enfoque discutido en este artículo
- Deje que el número tres sea a, b, c inicialice a 1
- Recorra la array de divisores y verifique la siguiente condición:
- valor de a = valor en el primer índice de la array de divisores.
- valor de b = producto del valor en el segundo y tercer índice de la array de divisores. Si la array de divisores tiene solo uno o dos elementos, entonces no existen tales tripletas
- Después de encontrar a & b, el valor de c = producto de todos los demás elementos en la array de divisores.
- Verifique la condición final tal que el valor de a, b, c debe ser distinto y no igual a 1.
A continuación se muestra el código de implementación:
CPP
// C++ program to find the
// three numbers
#include "bits/stdc++.h"
using namespace std;
// function to find 3 distinct number
// with given product
void getnumbers(int n)
{
// Declare a vector to store
// divisors
vector<int> divisor;
// store all divisors of number
// in array
for (int i = 2; i * i <= n; i++) {
// store all the occurrence of
// divisors
while (n % i == 0) {
divisor.push_back(i);
n /= i;
}
}
// check if n is not equals to -1
// then n is also a prime factor
if (n != 1) {
divisor.push_back(n);
}
// Initialize the variables with 1
int a, b, c, size;
a = b = c = 1;
size = divisor.size();
for (int i = 0; i < size; i++) {
// check for first number a
if (a == 1) {
a = a * divisor[i];
}
// check for second number b
else if (b == 1 || b == a) {
b = b * divisor[i];
}
// check for third number c
else {
c = c * divisor[i];
}
}
// check for all unwanted condition
if (a == 1 || b == 1 || c == 1
|| a == b || b == c || a == c) {
cout << "-1" << endl;
}
else {
cout << a << ' ' << b
<< ' ' << c << endl;
}
}
// Driver function
int main()
{
int n = 64;
getnumbers(n);
}
Java
// Java program to find the
// three numbers
import java.util.*;
class GFG{
// function to find 3 distinct number
// with given product
static void getnumbers(int n)
{
// Declare a vector to store
// divisors
Vector<Integer> divisor = new Vector<Integer>();
// store all divisors of number
// in array
for (int i = 2; i * i <= n; i++) {
// store all the occurrence of
// divisors
while (n % i == 0) {
divisor.add(i);
n /= i;
}
}
// check if n is not equals to -1
// then n is also a prime factor
if (n != 1) {
divisor.add(n);
}
// Initialize the variables with 1
int a, b, c, size;
a = b = c = 1;
size = divisor.size();
for (int i = 0; i < size; i++) {
// check for first number a
if (a == 1) {
a = a * divisor.get(i);
}
// check for second number b
else if (b == 1 || b == a) {
b = b * divisor.get(i);
}
// check for third number c
else {
c = c * divisor.get(i);
}
}
// check for all unwanted condition
if (a == 1 || b == 1 || c == 1
|| a == b || b == c || a == c) {
System.out.print("-1" +"\n");
}
else {
System.out.print(a +" "+ b
+" "+ c +"\n");
}
}
// Driver function
public static void main(String[] args)
{
int n = 64;
getnumbers(n);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to find the
# three numbers
# function to find 3 distinct number
# with given product
def getnumbers(n):
# Declare a vector to store
# divisors
divisor = []
# store all divisors of number
# in array
for i in range(2, n + 1):
# store all the occurrence of
# divisors
while (n % i == 0):
divisor.append(i)
n //= i
# check if n is not equals to -1
# then n is also a prime factor
if (n != 1):
divisor.append(n)
# Initialize the variables with 1
a, b, c, size = 0, 0, 0, 0
a = b = c = 1
size = len(divisor)
for i in range(size):
# check for first number a
if (a == 1):
a = a * divisor[i]
# check for second number b
elif (b == 1 or b == a):
b = b * divisor[i]
# check for third number c
else:
c = c * divisor[i]
# check for all unwanted condition
if (a == 1 or b == 1 or c == 1
or a == b or b == c or a == c):
print("-1")
else:
print(a, b, c)
# Driver function
n = 64
getnumbers(n)
# This code is contributed by mohit kumar 29
C#
// C# program to find the
// three numbers
using System;
using System.Collections.Generic;
class GFG{
// function to find 3 distinct number
// with given product
static void getnumbers(int n)
{
// Declare a vector to store
// divisors
List<int> divisor = new List<int>();
// store all divisors of number
// in array
for (int i = 2; i * i <= n; i++) {
// store all the occurrence of
// divisors
while (n % i == 0) {
divisor.Add(i);
n /= i;
}
}
// check if n is not equals to -1
// then n is also a prime factor
if (n != 1) {
divisor.Add(n);
}
// Initialize the variables with 1
int a, b, c, size;
a = b = c = 1;
size = divisor.Count;
for (int i = 0; i < size; i++) {
// check for first number a
if (a == 1) {
a = a * divisor[i];
}
// check for second number b
else if (b == 1 || b == a) {
b = b * divisor[i];
}
// check for third number c
else {
c = c * divisor[i];
}
}
// check for all unwanted condition
if (a == 1 || b == 1 || c == 1
|| a == b || b == c || a == c) {
Console.Write("-1" +"\n");
}
else {
Console.Write(a +" "+ b
+" "+ c +"\n");
}
}
// Driver function
public static void Main(String[] args)
{
int n = 64;
getnumbers(n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find the
// three numbers
// function to find 3 distinct number
// with given product
function getnumbers(n)
{
// Declare a vector to store
// divisors
let divisor = [];
// store all divisors of number
// in array
for (let i = 2; i * i <= n; i++) {
// store all the occurrence of
// divisors
while (n % i == 0) {
divisor.push(i);
n = Math.floor(n/i);
}
}
// check if n is not equals to -1
// then n is also a prime factor
if (n != 1) {
divisor.push(n);
}
// Initialize the variables with 1
let a, b, c, size;
a = b = c = 1;
size = divisor.length;
for (let i = 0; i < size; i++) {
// check for first number a
if (a == 1) {
a = a * divisor[i];
}
// check for second number b
else if (b == 1 || b == a) {
b = b * divisor[i];
}
// check for third number c
else {
c = c * divisor[i];
}
}
// check for all unwanted condition
if (a == 1 || b == 1 || c == 1
|| a == b || b == c || a == c) {
document.write("-1" +"<br>");
}
else {
document.write(a +" "+ b
+" "+ c +"<br>");
}
}
// Driver function
let n = 64;
getnumbers(n);
// This code is contributed by patel2127
</script>
Producción:
2 4 8
Complejidad de tiempo: O( (log N)*sqrt(N) )
Espacio auxiliar: O(sqrt(n))
Publicación traducida automáticamente
Artículo escrito por lalit kumar 7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA