Maximum length subsequence such that adjacent elements in the subsequence have a common factor | C # implementation of the above approach ; to compute least prime divisor of i ; 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
using System ; using System . Collections ; class GFG { static int N = 100005 ; static int MAX = 10000002 ; static int [ ] lpd = new int [ MAX ] ; static void preCompute ( ) { 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 ( int [ ] arr , int n ) { int [ ] dp = new int [ N ] ; Hashtable pos = new Hashtable ( ) ; 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 [ Convert . ToInt32 ( pos [ p ] ) ] ) ; } pos [ p ] = i ; while ( arr [ i ] % p == 0 ) arr [ i ] /= p ; } } int ans = 1 ; for ( int i = 0 ; i <= n ; i ++ ) { ans = Math . Max ( ans , dp [ i ] ) ; } return ans ; } public static void Main ( ) { int [ ] arr = { 13 , 2 , 8 , 6 , 3 , 1 , 9 } ; int n = arr . Length - 1 ; preCompute ( ) ; Console . WriteLine ( maxLengthSubsequence ( arr , n ) ) ; } }