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
< ? php function largestGCDSubsequence ( $ arr , $ n ) { $ ans = 0 ; $ maxele = max ( $ arr ) ; for ( $ i = 2 ; $ i <= $ maxele ; ++ $ i ) { $ count = 0 ; for ( $ j = 0 ; $ j < $ n ; ++ $ j ) { if ( $ arr [ $ j ] % $ i == 0 ) ++ $ count ; } $ ans = max ( $ ans , $ count ) ; } return $ ans ; } $ arr = array ( 3 , 6 , 2 , 5 , 4 ) ; $ size = count ( $ arr ) ; echo largestGCDSubsequence ( $ arr , $ size ) ; ? >