Largest subsequence having GCD greater than 1 | Efficient PHP 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
< ? php $ MAX = 10001 ; $ prime = array_fill ( 0 , $ MAX , 0 ) ; $ countdiv = array_fill ( 0 , $ MAX , 0 ) ; function SieveOfEratosthenes ( ) { global $ MAX , $ prime ; for ( $ i = 2 ; $ i * $ i <= $ MAX ; ++ $ i ) { if ( $ prime [ $ i ] == 0 ) for ( $ j = $ i * 2 ; $ j <= $ MAX ; $ j += $ i ) $ prime [ $ j ] = $ i ; } for ( $ i = 1 ; $ i < $ MAX ; ++ $ i ) if ( $ prime [ $ i ] == 0 ) $ prime [ $ i ] = $ i ; } function largestGCDSubsequence ( $ arr , $ n ) { global $ countdiv , $ prime ; $ ans = 0 ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) { $ element = $ arr [ $ i ] ; while ( $ element > 1 ) { $ div = $ prime [ $ element ] ; ++ $ countdiv [ $ div ] ; $ ans = max ( $ ans , $ countdiv [ $ div ] ) ; while ( $ element % $ div == 0 ) $ element = ( int ) ( $ element / $ div ) ; } } return $ ans ; } SieveOfEratosthenes ( ) ; $ arr = array ( 10 , 15 , 7 , 25 , 9 , 35 ) ; $ size = count ( $ arr ) ; echo largestGCDSubsequence ( $ arr , $ size ) ; ? >