Dado un número positivo n, necesitamos imprimir exactamente k números positivos (todos mayores que 1) tales que el producto de esos k números sea n. Si no existen tales números k, imprima -1 . Si hay muchas respuestas posibles, debe imprimir una de esas respuestas donde se ordenan los números k.
Ejemplos:
Input : n = 54, k = 3 Output : 2, 3, 9 Note that 2, 3 and 9 are k numbers with product equals to n. Input : n = 54, k = 8 Output : -1
Este problema usa una idea muy similar para imprimir todos los factores primos de un número dado .
La idea es muy simple. Primero calculamos todos los factores primos de n y los almacenamos en un vector. Tenga en cuenta que almacenamos cada número primo tantas veces como aparece en su descomposición en factores primos. Ahora, para encontrar k números mayores que 1, verificamos si el tamaño de nuestro vector es mayor o igual que k o no.
- Si el tamaño es menor que k imprimimos -1.
- De lo contrario, imprimimos los primeros k-1 factores como si fueran del vector y el último factor es el producto de todos los elementos restantes del vector.
Tenga en cuenta que insertamos todos los factores primos de manera ordenada, por lo tanto, todos nuestros números en el vector están ordenados. Esto también satisface nuestra condición ordenada para k números.
C++
// C++ program to find if it is possible to
// write a number n as product of exactly k
// positive numbers greater than 1.
#include <bits/stdc++.h>
using namespace std;
// Prints k factors of n if n can be written
// as multiple of k numbers. Else prints -1.
void kFactors(int n, int k)
{
// A vector to store all prime factors of n
vector<int> P;
// Insert all 2's in vector
while (n%2 == 0)
{
P.push_back(2);
n /= 2;
}
// n must be odd at this point
// So we skip one element (i = i + 2)
for (int i=3; i*i<=n; i=i+2)
{
while (n%i == 0)
{
n = n/i;
P.push_back(i);
}
}
// This is to handle when n > 2 and
// n is prime
if (n > 2)
P.push_back(n);
// If size(P) < k, k factors are not possible
if (P.size() < k)
{
cout << "-1" << endl;
return;
}
// printing first k-1 factors
for (int i=0; i<k-1; i++)
cout << P[i] << ", ";
// calculating and printing product of rest
// of numbers
int product = 1;
for (int i=k-1; i<P.size(); i++)
product = product*P[i];
cout << product << endl;
}
// Driver program to test above function
int main()
{
int n = 54, k = 3;
kFactors(n, k);
return 0;
}
Java
// Java program to find if it is possible to
// write a number n as product of exactly k
// positive numbers greater than 1.
import java.util.*;
class GFG
{
// Prints k factors of n if n can be written
// as multiple of k numbers. Else prints -1.
static void kFactors(int n, int k)
{
// A vector to store all prime factors of n
ArrayList<Integer> P = new ArrayList<Integer>();
// Insert all 2's in list
while (n % 2 == 0)
{
P.add(2);
n /= 2;
}
// n must be odd at this point
// So we skip one element (i = i + 2)
for (int i = 3; i * i <= n; i = i + 2)
{
while (n % i == 0)
{
n = n / i;
P.add(i);
}
}
// This is to handle when n > 2 and
// n is prime
if (n > 2)
P.add(n);
// If size(P) < k, k factors are
// not possible
if (P.size() < k)
{
System.out.println("-1");
return;
}
// printing first k-1 factors
for (int i = 0; i < k - 1; i++)
System.out.print(P.get(i) + ", ");
// calculating and printing product
// of rest of numbers
int product = 1;
for (int i = k - 1; i < P.size(); i++)
product = product * P.get(i);
System.out.println(product);
}
// Driver code
public static void main(String[] args)
{
int n = 54, k = 3;
kFactors(n, k);
}
}
// This code is contributed
// by chandan_jnu
Python3
# Python3 program to find if it is possible
# to write a number n as product of exactly k
# positive numbers greater than 1.
import math as mt
# Prints k factors of n if n can be written
# as multiple of k numbers. Else prints -1
def kFactors(n, k):
# list to store all prime factors of n
a = list()
#insert all 2's in list
while n % 2 == 0:
a.append(2)
n = n // 2
# n must be odd at this point
# so we skip one element(i=i+2)
for i in range(3, mt.ceil(mt.sqrt(n)), 2):
while n % i == 0:
n = n / i;
a.append(i)
# This is to handle when n>2 and
# n is prime
if n > 2:
a.append(n)
# if size(a)<k,k factors are not possible
if len(a) < k:
print("-1")
return
# printing first k-1 factors
for i in range(k - 1):
print(a[i], end = ", ")
# calculating and printing product
# of rest of numbers
product = 1
for i in range(k - 1, len(a)):
product *= a[i]
print(product)
# Driver code
n, k = 54, 3
kFactors(n, k)
# This code is contributed
# by mohit kumar 29
C#
// C# program to find if it is possible to
// write a number n as product of exactly k
// positive numbers greater than 1.
using System;
using System.Collections;
class GFG
{
// Prints k factors of n if n can be written
// as multiple of k numbers. Else prints -1.
static void kFactors(int n, int k)
{
// A vector to store all prime factors of n
ArrayList P = new ArrayList();
// Insert all 2's in list
while (n % 2 == 0)
{
P.Add(2);
n /= 2;
}
// n must be odd at this point
// So we skip one element (i = i + 2)
for (int i = 3; i * i <= n; i = i + 2)
{
while (n % i == 0)
{
n = n / i;
P.Add(i);
}
}
// This is to handle when n > 2 and
// n is prime
if (n > 2)
P.Add(n);
// If size(P) < k, k factors are not possible
if (P.Count < k)
{
Console.WriteLine("-1");
return;
}
// printing first k-1 factors
for (int i = 0; i < k - 1; i++)
Console.Write(P[i]+", ");
// calculating and printing product of rest
// of numbers
int product = 1;
for (int i = k - 1; i < P.Count; i++)
product = product*(int)P[i];
Console.WriteLine(product);
}
// Driver code
static void Main()
{
int n = 54, k = 3;
kFactors(n, k);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP program to find if it is possible to
// write a number n as product of exactly k
// positive numbers greater than 1.
// Prints k factors of n if n can be written
// as multiple of k numbers. Else prints -1.
function kFactors($n, $k)
{
// A vector to store all prime
// factors of n
$P = array();
// Insert all 2's in vector
while ($n % 2 == 0)
{
array_push($P, 2);
$n = (int)($n / 2);
}
// n must be odd at this point
// So we skip one element (i = i + 2)
for ($i = 3; $i * $i <= $n; $i = $i + 2)
{
while ($n % $i == 0)
{
$n = (int)($n / $i);
array_push($P, $i);
}
}
// This is to handle when n > 2 and
// n is prime
if ($n > 2)
array_push($P, $n);
// If size(P) < k, k factors are
// not possible
if (count($P) < $k)
{
echo "-1\n";
return;
}
// printing first k-1 factors
for ($i = 0; $i < $k - 1; $i++)
echo $P[$i] . ", ";
// calculating and printing product
// of rest of numbers
$product = 1;
for ($i = $k - 1; $i < count($P); $i++)
$product = $product * $P[$i];
echo $product;
}
// Driver Code
$n = 54;
$k = 3;
kFactors($n, $k);
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to find if it is possible to
// write a number n as product of exactly k
// positive numbers greater than 1.
// Prints k factors of n if n can be written
// as multiple of k numbers. Else prints -1.
function kFactors(n , k) {
// A vector to store all prime factors of n
var P = Array();
// Insert all 2's in list
while (n % 2 == 0) {
P.push(2);
n = parseInt(n/2);
}
// n must be odd at this point
// So we skip one element (i = i + 2)
for (i = 3; i * i <= n; i = i + 2) {
while (n % i == 0) {
n = parseInt(n/i);
P.push(i);
}
}
// This is to handle when n > 2 and
// n is prime
if (n > 2)
P.push(n);
// If size(P) < k, k factors are
// not possible
if (P.length < k) {
document.write("-1");
return;
}
// printing first k-1 factors
for (i = 0; i < k - 1; i++)
document.write(P[i] + ", ");
// calculating and printing product
// of rest of numbers
var product = 1;
for (i = k - 1; i < P.length; i++)
product = product * P[i];
document.write(product);
}
// Driver code
var n = 54, k = 3;
kFactors(n, k);
// This code is contributed by gauravrajput1
</script>
Producción:
2, 3, 9
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA