Maximum length subsequence such that adjacent elements in the subsequence have a common factor | C ++ implementation of the above approach ; Function 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
#include <bits/stdc++.h> NEW_LINE #define N  100005 NEW_LINE #define MAX  10000002 NEW_LINE using namespace std ; int lpd [ MAX ] ; void preCompute ( ) { memset ( lpd , 0 , sizeof ( lpd ) ) ; 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 ; } } } int maxLengthSubsequence ( int arr [ ] , int n ) { int dp [ N ] ; unordered_map < int , int > pos ; 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 [ p ] ) { dp [ i ] = max ( dp [ i ] , 1 + dp [ pos [ p ] ] ) ; } pos [ p ] = i ; while ( arr [ i ] % p == 0 ) arr [ i ] /= p ; } } int ans = 1 ; for ( int i = 0 ; i <= n ; i ++ ) { ans = max ( ans , dp [ i ] ) ; } return ans ; } int main ( ) { int arr [ ] = { 13 , 2 , 8 , 6 , 3 , 1 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; preCompute ( ) ; cout << maxLengthSubsequence ( arr , n ) ; return 0 ; }