Largest subsequence having GCD greater than 1 | Efficient Javascript 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 ; Pre - compute smallest divisor of all numbers
let MAX = 100001 ; let prime = new Array ( MAX + 1 ) ; let countdiv = new Array ( MAX + 1 ) ; for ( let i = 0 ; i < MAX + 1 ; i ++ ) { prime [ i ] = 0 ; countdiv [ i ] = 0 ; } function SieveOfEratosthenes ( ) { for ( let i = 2 ; i * i <= MAX ; ++ i ) { if ( prime [ i ] == 0 ) for ( let j = i * 2 ; j <= MAX ; j += i ) prime [ j ] = i ; } for ( let i = 1 ; i < MAX ; ++ i ) if ( prime [ i ] == 0 ) prime [ i ] = i ; } function largestGCDSubsequence ( arr , n ) { let ans = 0 ; for ( let i = 0 ; i < n ; ++ i ) { let element = arr [ i ] ; while ( element > 1 ) { let div = prime [ element ] ; ++ countdiv [ div ] ; ans = Math . max ( ans , countdiv [ div ] ) ; while ( element % div == 0 ) element /= div ; } } return ans ; } SieveOfEratosthenes ( ) ; let arr = [ 10 , 15 , 7 , 25 , 9 , 35 ] ; let size = arr . length ; document . write ( largestGCDSubsequence ( arr , size ) ) ;