Given a positive integer N, the task is to generate a sequence say arr[] of maximum length having all elements at least 2 such that the product of all the numbers in the sequence is N and for any pair of indices (i, j) and i < j, arr[j] is divisible by arr[i].
Examples:
Input: N = 360
Output: Maximum size = 3, final array = {2, 2, 90}
Explanation:
Consider the array arr[] be the resultant array, then the following operations can be performed:
- Add 2 to the array arr[]. Now, N = 360/2 = 180 and arr[] = {2}.
- Add 2 to the array arr[]. Now, N = 180/2 = 90 and arr[] = {2, 2}.
- Add 90 to the array arr[]. Now, arr[] = {2, 2, 90}.
After the above operations, the maximum size of the array is 3 and the resultant array is {2, 2, 90}.
Input: N = 810
Output: Maximum size = 4, final array = {3, 3, 3, 30}
Approach: The given problem can be solved by using the concept of prime factorization, the idea is to find the prime number having the maximum frequency of occurrence as N that can be represented as the product of prime numbers as:
N = (a1p1)*(a2p1)*(a3p1)*(a4p1)(……)*(anpn)
Follow the steps below to solve the problem:
- Initialize a Map, say M that stores all the prime numbers as a key and their powers as values. For example, for the value 23, the map M stores as M[2] = 3.
- Choose the prime factor which has the maximum power factor and store that power in a variable, say ans, and store that prime number in a variable say P.
- If the value of ans is smaller than 2, then the resultant array will be of size 1 and the array element will be equal to N.
- Otherwise, print the value of ans as the maximum length, and to print the final sequence, print the value of P (ans – 1) number of times, and then print (N/2ans) at the end.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the prime// factors of N with their countvector<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 sizevoid 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 Codeint main(){ int N = 360; printAnswer(N); return 0;} |
Java
// Java program for the above approachimport 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 countstatic 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 sizestatic 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 Codepublic static void main(String[] args){ int N = 360; printAnswer(N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachfrom math import sqrt# Function to calculate the prime# factors of N with their countdef 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 sizedef 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 Codeif __name__ == '__main__': N = 360 printAnswer(N) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing 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 countstatic 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 sizestatic 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 Codepublic 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 countfunction 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 sizefunction 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 Codelet N = 360;printAnswer(N);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
3 2 2 90
Time Complexity: O(N3/2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
