Dado un entero positivo N , la tarea es generar una secuencia, digamos arr[], de longitud máxima que tenga todos los elementos al menos 2, de modo que el producto de todos los números en la secuencia sea N y para cualquier par de índices (i, j) y i < j , arr[j] es divisible por arr[i] .
Ejemplos:
Entrada: N = 360
Salida: Tamaño máximo = 3, array final = {2, 2, 90}
Explicación:
Considere que la array arr[] es la array resultante, luego se pueden realizar las siguientes operaciones:
- Agregue 2 a la array arr[]. Ahora, N = 360/2 = 180 y arr[] = {2}.
- Agregue 2 a la array arr[]. Ahora, N = 180/2 = 90 y arr[] = {2, 2}.
- Agregue 90 a la array arr[]. Ahora, arr[] = {2, 2, 90}.
Después de las operaciones anteriores, el tamaño máximo de la array es 3 y la array resultante es {2, 2, 90}.
Entrada: N = 810
Salida: Tamaño máximo = 4, array final = {3, 3, 3, 30}
Enfoque: El problema dado se puede resolver utilizando el concepto de descomposición en factores primos , la idea es encontrar el número primo que tiene la máxima frecuencia de aparición como N que se puede representar como el producto de números primos como:
N = (a 1 p1 )*(a 2 p1 )*(a 3 p1 )*(a 4 p1 )(……)*(a n pn )
Siga los pasos a continuación para resolver el problema:
- Inicialice un Mapa , digamos M que almacena todos los números primos como una clave y sus potencias como valores. Por ejemplo, para el valor 2 3 , el mapa M almacena como M[2] = 3 .
- Elija el factor primo que tenga el factor de potencia máximo y almacene esa potencia en una variable, digamos ans , y almacene ese número primo en una variable digamos P .
- Si el valor de ans es menor que 2 , entonces la array resultante tendrá un tamaño de 1 y el elemento de la array será igual a N.
- De lo contrario, imprima el valor de ans como la longitud máxima y, para imprimir la secuencia final, imprima el valor de P (ans – 1) varias veces y luego imprima ( N/2 ans ) al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the prime
// factors of N with their count
vector<pair<int, int> > primeFactor(
int N)
{
// Initialize a vector, say v
vector<pair<int, int> > v;
// Initialize the count
int count = 0;
// Count the number of divisors
while (!(N % 2)) {
// Divide the value of N by 2
N >>= 1;
count++;
}
// For factor 2 divides it
if (count)
v.push_back({ 2, count });
// Find all prime factors
for (int i = 3;
i <= sqrt(N); i += 2) {
// Count their frequency
count = 0;
while (N % i == 0) {
count++;
N = N / i;
}
// Push it to the vector
if (count) {
v.push_back({ i, count });
}
}
// Push N if it is not 1
if (N > 2)
v.push_back({ N, 1 });
return v;
}
// Function to print the array that
// have the maximum size
void printAnswer(int n)
{
// Stores the all prime factor
// and their powers
vector<pair<int, int> > v
= primeFactor(n);
int maxi_size = 0, prime_factor = 0;
// Traverse the vector and find
// the maximum power of prime
// factor
for (int i = 0; i < v.size(); i++) {
if (maxi_size < v[i].second) {
maxi_size = v[i].second;
prime_factor = v[i].first;
}
}
// If max size is less than 2
if (maxi_size < 2) {
cout << 1 << ' ' << n;
}
// Otherwise
else {
int product = 1;
// Print the maximum size
// of sequence
cout << maxi_size << endl;
// Print the final sequence
for (int i = 0;
i < maxi_size - 1; i++) {
// Print the prime factor
cout << prime_factor << " ";
product *= prime_factor;
}
// Print the last value of
// the sequence
cout << (n / product);
}
}
// Driver Code
int main()
{
int N = 360;
printAnswer(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to calculate the prime
// factors of N with their count
static Vector<pair > primeFactor(
int N)
{
// Initialize a vector, say v
Vector<pair > v = new Vector<>();
// Initialize the count
int count = 0;
// Count the number of divisors
while ((N % 2)==0) {
// Divide the value of N by 2
N >>= 1;
count++;
}
// For factor 2 divides it
if (count!=0)
v.add(new pair( 2, count ));
// Find all prime factors
for (int i = 3;
i <= Math.sqrt(N); i += 2) {
// Count their frequency
count = 0;
while (N % i == 0) {
count++;
N = N / i;
}
// Push it to the vector
if (count!=0) {
v.add(new pair( i, count ));
}
}
// Push N if it is not 1
if (N > 2)
v.add(new pair( N, 1 ));
return v;
}
// Function to print the array that
// have the maximum size
static void printAnswer(int n)
{
// Stores the all prime factor
// and their powers
Vector<pair > v
= primeFactor(n);
int maxi_size = 0, prime_factor = 0;
// Traverse the vector and find
// the maximum power of prime
// factor
for (int i = 0; i < v.size(); i++) {
if (maxi_size < v.get(i).second) {
maxi_size = v.get(i).second;
prime_factor = v.get(i).first;
}
}
// If max size is less than 2
if (maxi_size < 2) {
System.out.print(1 << ' ');
}
// Otherwise
else {
int product = 1;
// Print the maximum size
// of sequence
System.out.print(maxi_size +"\n");
// Print the final sequence
for (int i = 0;
i < maxi_size - 1; i++) {
// Print the prime factor
System.out.print(prime_factor+ " ");
product *= prime_factor;
}
// Print the last value of
// the sequence
System.out.print((n / product));
}
}
// Driver Code
public static void main(String[] args)
{
int N = 360;
printAnswer(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach from math import sqrt # Function to calculate the prime # factors of N with their count def primeFactor(N): # Initialize a vector, say v v = [] # Initialize the count count = 0 # Count the number of divisors while ((N % 2) == 0): # Divide the value of N by 2 N >>= 1 count += 1 # For factor 2 divides it if (count): v.append([2, count]) # Find all prime factors for i in range(3, int(sqrt(N)) + 1, 2): # Count their frequency count = 0 while (N % i == 0): count += 1 N = N / i # Push it to the vector if (count): v.append([i, count]) # Push N if it is not 1 if (N > 2): v.append([N, 1]) return v # Function to print the array that # have the maximum size def printAnswer(n): # Stores the all prime factor # and their powers v = primeFactor(n) maxi_size = 0 prime_factor = 0 # Traverse the vector and find # the maximum power of prime # factor for i in range(len(v)): if (maxi_size < v[i][1]): maxi_size = v[i][1] prime_factor = v[i][0] # If max size is less than 2 if (maxi_size < 2): print(1, n) # Otherwise else: product = 1 # Print the maximum size # of sequence print(maxi_size) # Print the final sequence for i in range(maxi_size - 1): # Print the prime factor print(prime_factor, end = " ") product *= prime_factor # Print the last value of # the sequence print(n // product) # Driver Code if __name__ == '__main__': N = 360 printAnswer(N) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair
{
public int first;
public int second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to calculate the prime
// factors of N with their count
static List<pair > primeFactor(
int N)
{
// Initialize a vector, say v
List<pair > v = new List<pair>();
// Initialize the count
int count = 0;
// Count the number of divisors
while ((N % 2)==0) {
// Divide the value of N by 2
N >>= 1;
count++;
}
// For factor 2 divides it
if (count!=0)
v.Add(new pair( 2, count ));
// Find all prime factors
for (int i = 3;
i <= Math.Sqrt(N); i += 2) {
// Count their frequency
count = 0;
while (N % i == 0) {
count++;
N = N / i;
}
// Push it to the vector
if (count!=0) {
v.Add(new pair( i, count ));
}
}
// Push N if it is not 1
if (N > 2)
v.Add(new pair( N, 1 ));
return v;
}
// Function to print the array that
// have the maximum size
static void printAnswer(int n)
{
// Stores the all prime factor
// and their powers
List<pair > v
= primeFactor(n);
int maxi_size = 0, prime_factor = 0;
// Traverse the vector and find
// the maximum power of prime
// factor
for (int i = 0; i < v.Count; i++) {
if (maxi_size < v[i].second) {
maxi_size = v[i].second;
prime_factor = v[i].first;
}
}
// If max size is less than 2
if (maxi_size < 2) {
Console.Write(1 << ' ');
}
// Otherwise
else {
int product = 1;
// Print the maximum size
// of sequence
Console.Write(maxi_size +"\n");
// Print the readonly sequence
for (int i = 0;
i < maxi_size - 1; i++) {
// Print the prime factor
Console.Write(prime_factor+ " ");
product *= prime_factor;
}
// Print the last value of
// the sequence
Console.Write((n / product));
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 360;
printAnswer(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to calculate the prime
// factors of N with their count
function primeFactor(N)
{
// Initialize a vector, say v
let v = [];
// Initialize the count
let count = 0;
// Count the number of divisors
while (!(N % 2)) {
// Divide the value of N by 2
N >>= 1;
count++;
}
// For factor 2 divides it
if (count)
v.push([2, count]);
// Find all prime factors
for (let i = 3; i <= Math.sqrt(N); i += 2) {
// Count their frequency
count = 0;
while (N % i == 0) {
count++;
N = Math.floor(N / i);
}
// Push it to the vector
if (count) {
v.push([i, count]);
}
}
// Push N if it is not 1
if (N > 2)
v.push([N, 1]);
return v;
}
// Function to print the array that
// have the maximum size
function printAnswer(n)
{
// Stores the all prime factor
// and their powers
let v = primeFactor(n);
let maxi_size = 0, prime_factor = 0;
// Traverse the vector and find
// the maximum power of prime
// factor
for (let i = 0; i < v.length; i++) {
if (maxi_size < v[i][1]) {
maxi_size = v[i][1];
prime_factor = v[i][0];
}
}
// If max size is less than 2
if (maxi_size < 2) {
document.write(1 + ' ' + n);
}
// Otherwise
else {
let product = 1;
// Print the maximum size
// of sequence
document.write(maxi_size + "<br>");
// Print the final sequence
for (let i = 0; i < maxi_size - 1; i++) {
// Print the prime factor
document.write(prime_factor + " ");
product *= prime_factor;
}
// Print the last value of
// the sequence
document.write(Math.floor((n / product)));
}
}
// Driver Code
let N = 360;
printAnswer(N);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
3 2 2 90
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tier10coder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA