Longest subsequence such that every element in the subsequence is formed by multiplying previous element with a prime | Java 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
import java . util . HashMap ; import java . util . Vector ; class GFG { public static void SieveOfEratosthenes ( int MAX , Vector < Integer > 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 ) { HashMap < Integer , Integer > mpp = new HashMap < > ( ) ; Vector < Integer > primes = new Vector < > ( ) ; SieveOfEratosthenes ( A [ n - 1 ] , primes ) ; int [ ] dp = new int [ n ] ; dp [ n - 1 ] = 1 ; mpp . put ( A [ n - 1 ] , n - 1 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int num = A [ i ] ; dp [ i ] = 1 ; int maxi = 0 ; for ( int it : primes ) { int xx = num * it ; if ( xx > A [ n - 1 ] ) break ; else if ( mpp . get ( xx ) != null && mpp . get ( xx ) != 0 ) { dp [ i ] = Math . max ( dp [ i ] , 1 + dp [ mpp . get ( xx ) ] ) ; } } mpp . put ( 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 ; System . out . println ( findLongest ( a , n ) ) ; } }