Largest subsequence having GCD greater than 1 | Returns length of the largest subsequence with GCD more than 1. ; Finding the Maximum value in arr [ ] ; Iterate from 2 to maximum possible divisor of all give values ; If we found divisor , increment count ; Driver code
def largestGCDSubsequence ( arr , n ) : NEW_LINE INDENT ans = 0 NEW_LINE maxele = max ( arr ) NEW_LINE for i in range ( 2 , maxele + 1 ) : NEW_LINE INDENT count = 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( arr [ j ] % i == 0 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT ans = max ( ans , count ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 6 , 2 , 5 , 4 ] NEW_LINE size = len ( arr ) NEW_LINE print ( largestGCDSubsequence ( arr , size ) ) NEW_LINE DEDENT