Generate longest possible array with product K such that each array element is divisible by its previous adjacent element | 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
def findLongestArray ( K ) : NEW_LINE INDENT primefactors = [ ] NEW_LINE K_temp = K NEW_LINE i = 2 NEW_LINE while i * i <= K : NEW_LINE INDENT count = 0 NEW_LINE while ( K_temp % i == 0 ) : NEW_LINE INDENT K_temp //= i NEW_LINE count += 1 NEW_LINE DEDENT if ( count > 0 ) : NEW_LINE INDENT primefactors . append ( [ count , i ] ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if ( K_temp != 1 ) : NEW_LINE INDENT primefactors . append ( [ 1 , K_temp ] ) NEW_LINE DEDENT primefactors . sort ( ) NEW_LINE answer = [ primefactors [ 0 ] [ 0 ] , primefactors [ 0 ] [ 1 ] ] NEW_LINE answer [ - 1 ] *= K NEW_LINE for i in range ( primefactors [ 0 ] [ 0 ] ) : NEW_LINE INDENT answer [ - 1 ] //= primefactors [ 0 ] [ 1 ] NEW_LINE DEDENT print ( " { " , end = " " ) NEW_LINE for i in range ( len ( answer ) ) : NEW_LINE INDENT if ( i == len ( answer ) - 1 ) : NEW_LINE INDENT print ( answer [ i ] , end = " } " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( answer [ i ] , end = " , ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT K = 4 NEW_LINE findLongestArray ( K ) NEW_LINE DEDENT