Generate a sequence with product N such that for every pair of indices ( i , j ) and i < j , arr [ j ] is divisible by arr [ i ] | C ++ program for the above approach ; Function to calculate the prime factors of N with their count ; Initialize a vector , say v ; Initialize the count ; Count the number of divisors ; Divide the value of N by 2 ; For factor 2 divides it ; Find all prime factors ; Count their frequency ; Push it to the vector ; Push N if it is not 1 ; Function to print the array that have the maximum size ; Stores the all prime factor and their powers ; Traverse the vector and find the maximum power of prime factor ; If max size is less than 2 ; Otherwise ; Print the maximum size of sequence ; Print the final sequence ; Print the prime factor ; Print the last value of the sequence ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < pair < int , int > > primeFactor ( int N ) { vector < pair < int , int > > v ; int count = 0 ; while ( ! ( N % 2 ) ) { N >>= 1 ; count ++ ; } if ( count ) v . push_back ( { 2 , count } ) ; for ( int i = 3 ; i <= sqrt ( N ) ; i += 2 ) { count = 0 ; while ( N % i == 0 ) { count ++ ; N = N / i ; } if ( count ) { v . push_back ( { i , count } ) ; } } if ( N > 2 ) v . push_back ( { N , 1 } ) ; return v ; } void printAnswer ( int n ) { vector < pair < int , int > > v = primeFactor ( n ) ; int maxi_size = 0 , prime_factor = 0 ; 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 ( maxi_size < 2 ) { cout << 1 << ' ▁ ' << n ; } else { int product = 1 ; cout << maxi_size << endl ; for ( int i = 0 ; i < maxi_size - 1 ; i ++ ) { cout << prime_factor << " ▁ " ; product *= prime_factor ; } cout << ( n / product ) ; } } int main ( ) { int N = 360 ; printAnswer ( N ) ; return 0 ; }