Maximum length subsequence such that adjacent elements in the subsequence have a common factor | Python3 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
import math as mt NEW_LINE N = 100005 NEW_LINE MAX = 1000002 NEW_LINE lpd = [ 0 for i in range ( MAX ) ] NEW_LINE def preCompute ( ) : NEW_LINE INDENT lpd [ 0 ] , lpd [ 1 ] = 1 , 1 NEW_LINE for i in range ( 2 , mt . ceil ( mt . sqrt ( MAX ) ) ) : NEW_LINE INDENT for j in range ( 2 * i , MAX , i ) : NEW_LINE INDENT if ( lpd [ j ] == 0 ) : NEW_LINE INDENT lpd [ j ] = i NEW_LINE DEDENT DEDENT DEDENT for i in range ( 2 , MAX ) : NEW_LINE INDENT if ( lpd [ i ] == 0 ) : NEW_LINE INDENT lpd [ i ] = i NEW_LINE DEDENT DEDENT DEDENT def maxLengthSubsequence ( arr , n ) : NEW_LINE INDENT dp = [ 1 for i in range ( N + 1 ) ] NEW_LINE pos = dict ( ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT while ( arr [ i ] > 1 ) : NEW_LINE INDENT p = lpd [ arr [ i ] ] NEW_LINE if ( p in pos . keys ( ) ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , 1 + dp [ pos [ p ] ] ) NEW_LINE DEDENT pos [ p ] = i NEW_LINE while ( arr [ i ] % p == 0 ) : NEW_LINE INDENT arr [ i ] //= p NEW_LINE DEDENT DEDENT DEDENT ans = 1 NEW_LINE for i in range ( 0 , n + 1 ) : NEW_LINE INDENT ans = max ( ans , dp [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 13 , 2 , 8 , 6 , 3 , 1 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE preCompute ( ) NEW_LINE print ( maxLengthSubsequence ( arr , n ) ) NEW_LINE