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 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( int MAX , vector < int > & primes ) { bool prime [ MAX + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( long long p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( long long i = p * p ; i <= MAX ; i += p ) prime [ i ] = false ; } } for ( long long i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] ) primes . push_back ( i ) ; } } int findLongest ( int A [ ] , int n ) { unordered_map < int , int > mpp ; vector < int > primes ; SieveOfEratosthenes ( A [ n - 1 ] , primes ) ; int dp [ n ] ; memset ( dp , 0 , sizeof dp ) ; dp [ n - 1 ] = 1 ; mpp [ A [ n - 1 ] ] = n - 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int num = A [ i ] ; dp [ i ] = 1 ; int maxi = 0 ; for ( auto it : primes ) { int xx = num * it ; if ( xx > A [ n - 1 ] ) break ; else if ( mpp [ xx ] != 0 ) { dp [ i ] = max ( dp [ i ] , 1 + dp [ mpp [ xx ] ] ) ; } } mpp [ A [ i ] ] = i ; } int ans = 1 ; for ( int i = 0 ; i < n ; i ++ ) { ans = max ( ans , dp [ i ] ) ; } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 5 , 6 , 12 , 35 , 60 , 385 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << findLongest ( a , n ) ; }