Largest subsequence having GCD greater than 1 | Simple C ++ program to find length of the largest subsequence with 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int largestGCDSubsequence ( int arr [ ] , int n ) { int ans = 0 ; int maxele = * max_element ( arr , arr + n ) ; for ( int i = 2 ; i <= maxele ; ++ i ) { int count = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( arr [ j ] % i == 0 ) ++ count ; } ans = max ( ans , count ) ; } return ans ; } int main ( ) { int arr [ ] = { 3 , 6 , 2 , 5 , 4 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << largestGCDSubsequence ( arr , size ) ; return 0 ; }