Generate longest possible array with product K such that each array element is divisible by its previous adjacent element | java 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void findLongestArray ( int K ) { ArrayList < int [ ] > primefactors = new ArrayList < > ( ) ; 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 . add ( new int [ ] { count , i } ) ; } if ( K_temp != 1 ) primefactors . add ( new int [ ] { 1 , K_temp } ) ; Collections . sort ( primefactors , ( x , y ) -> { if ( x [ 0 ] != y [ 0 ] ) return y [ 0 ] - x [ 0 ] ; return y [ 1 ] - x [ 1 ] ; } ) ; int n = primefactors . get ( 0 ) [ 0 ] ; int val = primefactors . get ( 0 ) [ 1 ] ; int answer [ ] = new int [ n ] ; Arrays . fill ( answer , val ) ; answer [ n - 1 ] *= K ; for ( int i = 0 ; i < n ; i ++ ) { answer [ n - 1 ] /= val ; } System . out . print ( " { " ) ; for ( int i = 0 ; i < answer . length ; i ++ ) { if ( i == answer . length - 1 ) System . out . print ( answer [ i ] + " } " ) ; else System . out . print ( answer [ i ] + " , ▁ " ) ; } } public static void main ( String [ ] args ) { int K = 4 ; findLongestArray ( K ) ; } }