Maximum length subsequence such that adjacent elements in the subsequence have a common factor | Java implementation of the above approach ; Function to compute least prime divisor of i upto MAX element of the input array it will be space efficient if more test cases are there it 's  better to find prime divisor  upto upperbound of input element  it will be cost efficient ; Function that returns the maximum length subsequence such that adjacent elements have a common factor . ; Initialize dp array with 1. ; p has appeared at least once . ; Update latest occurrence of prime p . ; Take maximum value as the answer . ; Driver code
import java . util . * ; class GfG { static int N , MAX ; static int lpd [ ] ; static void preCompute ( ) { lpd = new int [ MAX + 1 ] ; lpd [ 0 ] = lpd [ 1 ] = 1 ; for ( int i = 2 ; i * i <= MAX ; i ++ ) { for ( int j = i * 2 ; j <= MAX ; j += i ) { if ( lpd [ j ] == 0 ) { lpd [ j ] = i ; } } } for ( int i = 2 ; i <= MAX ; i ++ ) { if ( lpd [ i ] == 0 ) { lpd [ i ] = i ; } } } static int maxLengthSubsequence ( Integer arr [ ] , int n ) { Integer dp [ ] = new Integer [ N ] ; Map < Integer , Integer > pos = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i <= n ; i ++ ) dp [ i ] = 1 ; for ( int i = 0 ; i <= n ; i ++ ) { while ( arr [ i ] > 1 ) { int p = lpd [ arr [ i ] ] ; if ( pos . containsKey ( p ) ) { dp [ i ] = Math . max ( dp [ i ] , 1 + dp [ pos . get ( p ) ] ) ; } pos . put ( p , i ) ; while ( arr [ i ] % p == 0 ) arr [ i ] /= p ; } } int ans = Collections . max ( Arrays . asList ( dp ) ) ; return ans ; } public static void main ( String [ ] args ) { Integer arr [ ] = { 12 , 2 , 8 , 6 , 3 , 1 , 9 } ; N = arr . length ; MAX = Collections . max ( Arrays . asList ( arr ) ) ; preCompute ( ) ; System . out . println ( maxLengthSubsequence ( arr , N - 1 ) ) ; } }