text: Longest subsequence such that every element in the subsequence is formed by multiplying previous element with a prime | C # program to implement the above approach ; Function to pre - store primes ; Sieve method to check if prime or not ; Multiples ; Pre - store all the primes ; Function to find the intest subsequence ; Hash map ; Call the function to pre - store the primes ; Initialize last element with 1 as that is the intest possible ; Iterate from the back and find the intest ; 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 intest ; Driver code
code: using System ; using System . Collections . Generic ; class GFG { public static void SieveOfEratosthenes ( int MAX , List < int > primes ) { Boolean [ ] prime = new Boolean [ MAX + 1 ] ; for ( int i = 0 ; i < MAX + 1 ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= MAX ; i += p ) prime [ i ] = false ; } } for ( int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] ) primes . Add ( i ) ; } } public static int findLongest ( int [ ] A , int n ) { Dictionary < int , int > mpp = new Dictionary < int , int > ( ) ; List < int > primes = new List < int > ( ) ; SieveOfEratosthenes ( A [ n - 1 ] , primes ) ; int [ ] dp = new int [ n ] ; dp [ n - 1 ] = 1 ; mpp . Add ( A [ n - 1 ] , n - 1 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int num = A [ i ] ; dp [ i ] = 1 ; foreach ( int it in primes ) { int xx = num * it ; if ( xx > A [ n - 1 ] ) break ; else if ( mpp . ContainsKey ( xx ) && mpp [ xx ] != 0 ) { dp [ i ] = Math . Max ( dp [ i ] , 1 + dp [ mpp [ xx ] ] ) ; } } if ( mpp . ContainsKey ( A [ i ] ) ) mpp [ A [ i ] ] = i ; else mpp . Add ( A [ i ] , i ) ; } int ans = 1 ; for ( int i = 0 ; i < n ; i ++ ) ans = Math . Max ( ans , dp [ i ] ) ; return ans ; } public static void Main ( String [ ] args ) { int [ ] a = { 1 , 2 , 5 , 6 , 12 , 35 , 60 , 385 } ; int n = a . Length ; Console . WriteLine ( findLongest ( a , n ) ) ; } }