Largest subsequence having GCD greater than 1 | Efficient Java program to find length of the largest subsequence with GCD greater than 1. ; prime [ ] for storing smallest prime divisor of element count [ ] for storing the number of times a particular divisor occurs in a subsequence ; Simple sieve to find smallest prime factors of numbers smaller than MAX ; Prime number will have same divisor ; Returns length of the largest subsequence with GCD more than 1. ; Fetch total unique prime divisor of element ; Increment count [ ] of Every unique divisor we get till now ; Find maximum frequency of divisor ; Driver code ; Pre - compute smallest divisor of all numbers
class GFG { static int MAX = 100001 ; static int [ ] prime = new int [ MAX + 1 ] ; static int [ ] countdiv = new int [ MAX + 1 ] ; static void SieveOfEratosthenes ( ) { for ( int i = 2 ; i * i <= MAX ; ++ i ) { if ( prime [ i ] == 0 ) for ( int j = i * 2 ; j <= MAX ; j += i ) prime [ j ] = i ; } for ( int i = 1 ; i < MAX ; ++ i ) if ( prime [ i ] == 0 ) prime [ i ] = i ; } static int largestGCDSubsequence ( int arr [ ] , int n ) { int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int element = arr [ i ] ; while ( element > 1 ) { int div = prime [ element ] ; ++ countdiv [ div ] ; ans = Math . max ( ans , countdiv [ div ] ) ; while ( element % div == 0 ) element /= div ; } } return ans ; } public static void main ( String [ ] args ) { SieveOfEratosthenes ( ) ; int arr [ ] = { 10 , 15 , 7 , 25 , 9 , 35 } ; int size = arr . length ; System . out . println ( largestGCDSubsequence ( arr , size ) ) ; } }