Generate longest possible array with product K such that each array element is divisible by its previous adjacent element | C ++ program for the above approach ; Function to construct longest array with product K such that each element is divisible by its previous element ; Stores the prime factors of K ; Stores the power to which primefactor i is raised ; Sort prime factors in descending order ; Stores the final array ; Multiply the last element by K ; Print the constructed array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findLongestArray ( int K ) { vector < pair < int , int > > primefactors ; int K_temp = K ; for ( int i = 2 ; i * i <= K ; i ++ ) { int count = 0 ; while ( K_temp % i == 0 ) { K_temp /= i ; count ++ ; } if ( count > 0 ) primefactors . push_back ( { count , i } ) ; } if ( K_temp != 1 ) primefactors . push_back ( { 1 , K_temp } ) ; sort ( primefactors . rbegin ( ) , primefactors . rend ( ) ) ; vector < int > answer ( primefactors [ 0 ] . first , primefactors [ 0 ] . second ) ; answer . back ( ) *= K ; for ( int i = 0 ; i < primefactors [ 0 ] . first ; i ++ ) { answer . back ( ) /= primefactors [ 0 ] . second ; } cout << " { " ; for ( int i = 0 ; i < ( int ) answer . size ( ) ; i ++ ) { if ( i == answer . size ( ) - 1 ) cout << answer [ i ] << " } " ; else cout << answer [ i ] << " , ▁ " ; } } int main ( ) { int K = 4 ; findLongestArray ( K ) ; }