Longest subsequence such that every element in the subsequence is formed by multiplying previous element with a prime | Function to pre - store primes ; Sieve method to check if prime or not ; Multiples ; Pre - store all the primes ; Function to find the longest subsequence ; Hash map ; Call the function to pre - store the primes ; Initialize last element with 1 as that is the longest possible ; Iterate from the back and find the longest ; Get the number ; Initialize dp [ i ] as 1 as the element will only me in the subsequence . ; Iterate in all the primes and multiply to get the next element ; Next element if multiplied with it ; If exceeds the last element then break ; If the number is there in the array ; Get the maximum most element ; Hash the element ; Find the longest ; Driver Code
function SieveOfEratosthenes ( MAX , primes ) { let prime = new Array ( MAX + 1 ) . fill ( true ) ; for ( let p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( let i = p * p ; i <= MAX ; i += p ) prime [ i ] = false ; } } for ( let i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] ) primes . push ( i ) ; } } function findLongest ( A , n ) { let mpp = new Map ( ) ; let primes = new Array ( ) ; SieveOfEratosthenes ( A [ n - 1 ] , primes ) ; let dp = new Array ( n ) ; dp . fill ( 0 ) dp [ n - 1 ] = 1 ; mpp . set ( A [ n - 1 ] , n - 1 ) ; for ( let i = n - 2 ; i >= 0 ; i -- ) { let num = A [ i ] ; dp [ i ] = 1 ; let maxi = 0 ; for ( let it of primes ) { let xx = num * it ; if ( xx > A [ n - 1 ] ) break ; else if ( mpp . get ( xx ) ) { dp [ i ] = Math . max ( dp [ i ] , 1 + dp [ mpp . get ( xx ) ] ) ; } } mpp . set ( A [ i ] , i ) ; } let ans = 1 ; for ( let i = 0 ; i < n ; i ++ ) { ans = Math . max ( ans , dp [ i ] ) ; } return ans ; } let a = [ 1 , 2 , 5 , 6 , 12 , 35 , 60 , 385 ] ; let n = a . length ; document . write ( findLongest ( a , n ) ) ;